NYOJ 311完全リュック【ちょうど完全リュックがいっぱい】

完全リュックサック
時間制限:
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である.

#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;
}