欲張りアルゴリズムのカリブ海賊船の最適積載問題
940 ワード
1、問題
北アメリカ南東部には神秘的な海域があり、そこは碧海が青空で太陽の光が明るい.これは伝説の中で海賊が最も活発なカリブ海である.ここはヨーロッパ大陸の商旅艦隊がアメリカに到着する必経の地である.だから当時の海賊活王立艦は......海賊は昔の商人だけでなく、イギリスを攻撃したある日、海賊たちはいろいろな骨董品がいっぱい入った貨物船を捕獲し、骨董品ごとに価値があり、砕くと価値を失った.海賊船は十分な大きさですが、積載重量はCで、骨董品ごとの重量はw iです.海賊たちはどのようにしてできるだけ多くの宝物を海賊船に積むのでしょうか.
2、分析
ここのすべての品物の価値に注意して、私达は貪欲なアルゴリズムを使うことができて、最も肯定的に最も良く置くことができて、私达は毎回最小の重量の骨董品から置くことができて、未知を置くことができませんまで
まずソートします.そして毎回最小の重量の骨董品を入れます.
貪欲な策略:毎回最小の重量の骨董品を入れます
3、コード実現
一般的な実装:
北アメリカ南東部には神秘的な海域があり、そこは碧海が青空で太陽の光が明るい.これは伝説の中で海賊が最も活発なカリブ海である.ここはヨーロッパ大陸の商旅艦隊がアメリカに到着する必経の地である.だから当時の海賊活王立艦は......海賊は昔の商人だけでなく、イギリスを攻撃したある日、海賊たちはいろいろな骨董品がいっぱい入った貨物船を捕獲し、骨董品ごとに価値があり、砕くと価値を失った.海賊船は十分な大きさですが、積載重量はCで、骨董品ごとの重量はw iです.海賊たちはどのようにしてできるだけ多くの宝物を海賊船に積むのでしょうか.
2、分析
ここのすべての品物の価値に注意して、私达は貪欲なアルゴリズムを使うことができて、最も肯定的に最も良く置くことができて、私达は毎回最小の重量の骨董品から置くことができて、未知を置くことができませんまで
まずソートします.そして毎回最小の重量の骨董品を入れます.
貪欲な策略:毎回最小の重量の骨董品を入れます
3、コード実現
一般的な実装:
#include
#include
using namespace std;
// const int M 1000;
// ,
const int M = 1000;
double data[M];
int main()
{
std::cout << " ( 1000)" << std::endl;
//all ,count
int weight = 0, all = 0, count = 0;
std::cin >> weight >> all;
if (weight <= 0 || all <= 0 || all > 1000)
{
std::cout <<