114.完全リュック【完全リュックサックがぎっしり詰まっている
2051 ワード
完全リュックサック
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
4
説明
直接に言えば、完全なリュックサックにはN種類のものとV容量のリュックサックが定義されており、それぞれのものには無限のものがあります.i番目の品物の体積はcで、価値はwです.リュックサックにどのアイテムを入れるかを解くと、これらのアイテムの体積の合計がリュックサックの容量を超えず、価値の合計が最大になります.本題では、リュックサックがリュックサックにぴったり詰まっているときに、最大価値の総和を求めることが求められています.リュックがぴったり詰まっていなければ、NOを出力します
入力
1行目:Nは、テストデータのセット数(N<7)を示す.
次に、各試験データの最初の行には、2つの整数M、Vがある.Mは品物の種類の数を表し、Vはリュックサックの総容量を表す.(0
次のM行は行ごとに2つの整数cがあり、wはそれぞれ各物品の重量と価値を表す(0
しゅつりょく
テストデータの各セットに対応して結果を出力します(リュックサックが適切に満たされていれば、リュックサックが満たされているときのリュックサック内の物品の最大価値の合計を出力します.リュックサックが適切に満たされていなければ、NOを出力します).
サンプル入力
サンプル出力
アップロード者
ACM_趙銘浩
ここではf配列を極小負値に初期化して満タンであるか否かを判断するがf[0]=0である.
[cpp] view plain
copy
#include
#include
#include
#define maxn 2020
using namespace std;
int c[maxn],w[maxn],f[50050];
int main()
{
int n,m,v;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&m,&v);
for(int i=1;i<=m;++i)
scanf("%d%d",&c[i],&w[i]);
memset(f,0,sizeof(f));
for(int i=1;i<=v;++i)
f[i]=-999999;//ここでは-1000でWA for(int i=1;i<=m;++i)
{
for(int j=c[i];j<=v;++j)
f[j]=f[j]>f[j-c[i]]+w[i]?f[j]:f[j-c[i]]+w[i];
}
if(f[v]<0)
printf("NO");
else
printf("%d",f[v]);
}
return 0;
}
初期化の詳細:
ある問題では「リュックサックがぴったり詰まっている」という要求があり,あるものは要求がなく,DP配列を初期化する際に異なる.
ちょうどリュックサックがいっぱい:初期化時、DP[0]=0、その他のDP[1.....V]はいずれも負の無限大とする.
リュックサックを適切に満たす必要はありません:初期化時、DP[1.....V]はすべて0に設定します.
転載先:https://www.cnblogs.com/c1299401227/p/5370698.html
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
4
説明
直接に言えば、完全なリュックサックにはN種類のものとV容量のリュックサックが定義されており、それぞれのものには無限のものがあります.i番目の品物の体積はcで、価値はwです.リュックサックにどのアイテムを入れるかを解くと、これらのアイテムの体積の合計がリュックサックの容量を超えず、価値の合計が最大になります.本題では、リュックサックがリュックサックにぴったり詰まっているときに、最大価値の総和を求めることが求められています.リュックがぴったり詰まっていなければ、NOを出力します
入力
1行目:Nは、テストデータのセット数(N<7)を示す.
次に、各試験データの最初の行には、2つの整数M、Vがある.Mは品物の種類の数を表し、Vはリュックサックの総容量を表す.(0
次のM行は行ごとに2つの整数cがあり、wはそれぞれ各物品の重量と価値を表す(0
しゅつりょく
テストデータの各セットに対応して結果を出力します(リュックサックが適切に満たされていれば、リュックサックが満たされているときのリュックサック内の物品の最大価値の合計を出力します.リュックサックが適切に満たされていなければ、NOを出力します).
サンプル入力
2
1 5
2 2
2 5
2 2
5 1
サンプル出力
NO
1
アップロード者
ACM_趙銘浩
ここではf配列を極小負値に初期化して満タンであるか否かを判断するがf[0]=0である.
[cpp] view plain
copy
#include
#include
#include
#define maxn 2020
using namespace std;
int c[maxn],w[maxn],f[50050];
int main()
{
int n,m,v;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&m,&v);
for(int i=1;i<=m;++i)
scanf("%d%d",&c[i],&w[i]);
memset(f,0,sizeof(f));
for(int i=1;i<=v;++i)
f[i]=-999999;//ここでは-1000でWA for(int i=1;i<=m;++i)
{
for(int j=c[i];j<=v;++j)
f[j]=f[j]>f[j-c[i]]+w[i]?f[j]:f[j-c[i]]+w[i];
}
if(f[v]<0)
printf("NO");
else
printf("%d",f[v]);
}
return 0;
}
初期化の詳細:
ある問題では「リュックサックがぴったり詰まっている」という要求があり,あるものは要求がなく,DP配列を初期化する際に異なる.
ちょうどリュックサックがいっぱい:初期化時、DP[0]=0、その他のDP[1.....V]はいずれも負の無限大とする.
リュックサックを適切に満たす必要はありません:初期化時、DP[1.....V]はすべて0に設定します.
転載先:https://www.cnblogs.com/c1299401227/p/5370698.html