NY 311完全リュック問題

1725 ワード

完全リュックサック
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
4
説明
直接に言えば、完全なリュックサックにはN種類のものとV容量のリュックサックが定義されており、それぞれのものには無限のものがあります.i番目の品物の体積はcで、価値はwです.リュックサックにどのアイテムを入れるかを解くと、これらのアイテムの体積の合計がリュックサックの容量を超えず、価値の合計が最大になります.本題では、リュックサックがリュックサックにぴったり詰まっているときに、最大価値の総和を求めることが求められています.リュックがぴったり詰まっていなければ、NOを出力します
入力
1行目:Nは、テストデータのセット数(N<7)を示す.
次に、各試験データの最初の行には、2つの整数M、Vがある.Mは品物の種類の数を表し、Vはリュックサックの総容量を表す.(0次のM行には1行あたり2つの整数cがあり、wはそれぞれ各物品の重量と価値(0しゅつりょく
テストデータの各セットに対応して結果を出力します(リュックサックが適切に満たされていれば、リュックサックが満たされているときのリュックサック内の物品の最大価値の合計を出力します.リュックサックが適切に満たされていなければ、NOを出力します).
サンプル入力

サンプル出力

NO
1

解題構想:空間圧縮後の01リュックと同じ
状態遷移方程式:dp[j]=MAX(dp[j],(dp[j-c]+worth);
少し違うだけで、
for(j=c;j<=v;j++)
ここは順押しです.
01リュックサックは逆押しです.
この时、すべての品物を満たす无限のものが入っているからです.の
参考:リュックサック九講のp 02

#include <stdio.h>
#include <string.h>
#define MAX(a,b) a>b?a:b
int dp[50001];
int main()
{
    int n,m,v,c,worth,i,j;
    scanf("%d",&n);
    while(n--)
    {
        memset(dp,-10000,sizeof(dp));//      
        scanf("%d%d",&m,&v);
        dp[0] = 0;//   dp
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&c,&worth);
            for(j=c;j<=v;j++)//  01        
            {
                dp[j] = MAX(dp[j],(dp[j-c] + worth));
            }
        }
        if(dp[v] >= 0)
            printf("%d
",dp[v]);
        else
            printf("NO
");
    }
    return 0;
}

UVa 10491 Cows and Cars(確率計算)

データ構造の簡単なメモ