趣学アルゴリズムNYOJカリブ海賊船
4924 ワード
北アメリカ南東部には神秘的な海域があり、そこには青空があり、日光が明るい.伝説の海賊が最も活躍したカリブ海(Caribbean Sea).17世紀にはヨーロッパ大陸の商旅艦隊がアメリカに到着する必経の地だったため、当時の海賊活動が横行し、海賊は過去の商人だけでなく、英国の王立艦まで攻撃した.
ある日、海賊たちはいろいろな骨董品がいっぱい入った貨物船を捕まえた.骨董品は価値があり、砕くと価値を失った.海賊船は十分大きいが、積載重量はC、骨董品1枚あたりの重量はwiで、海賊たちはどのようにしてできるだけ多くの宝物を海賊船に積むのだろうか.
入力説明:第1行は、m群のテストデータを共有する整数m(m<100)である.各テストデータの最初の行は2つの整数cであり、n(1第2行目はn個の数であり、それぞれ第i個目のアンティークの重量を表す.出力記述:各組の入力に対して、入力可能なアンティークの最大数を出力する.各組の出力は1行のサンプル入力を占める:コピー2 30 8 4 10 7 7 7 7 11 3 5 14 2 45 10 5 12 7 3 20 9 15 11 8 32サンプル出力:5 6この問題は比較的簡単で、重量をソートするだけで、その後tmp変数は小さい頃から大きな現在の累積の和は、制限された重量と比較して、小さくさえあればcnt++を、これ以上物を入れられないまで、最後に答えを得ることができます.
ある日、海賊たちはいろいろな骨董品がいっぱい入った貨物船を捕まえた.骨董品は価値があり、砕くと価値を失った.海賊船は十分大きいが、積載重量はC、骨董品1枚あたりの重量はwiで、海賊たちはどのようにしてできるだけ多くの宝物を海賊船に積むのだろうか.
入力説明:第1行は、m群のテストデータを共有する整数m(m<100)である.各テストデータの最初の行は2つの整数cであり、n(1第2行目はn個の数であり、それぞれ第i個目のアンティークの重量を表す.出力記述:各組の入力に対して、入力可能なアンティークの最大数を出力する.各組の出力は1行のサンプル入力を占める:コピー2 30 8 4 10 7 7 7 7 11 3 5 14 2 45 10 5 12 7 3 20 9 15 11 8 32サンプル出力:5 6この問題は比較的簡単で、重量をソートするだけで、その後tmp変数は小さい頃から大きな現在の累積の和は、制限された重量と比較して、小さくさえあればcnt++を、これ以上物を入れられないまで、最後に答えを得ることができます.
#include
#include
using namespace std;
int main(){
int num;
int weight,shu;
int value[10001];
cin>>num;
while(num--){
cin>>weight>>shu;
for(int i=0;i<shu;i++)
cin>>value[i];
sort(value,value+shu);
int tmp=0;
int cnt=0;
for(int i=0;i<shu;i++){
if(tmp<=weight){
if(tmp+value[i]<=weight){
tmp+=value[i];
cnt++;
}
}
}
cout<<cnt<<endl;
}
return 0;
}