南陽-289-りんご(0-1リュックサック問題)

りんご
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
3
説明
ctestにはn個のリンゴがあり、容量vのリュックサックに入れます.i番目のりんごの大きさと値段をあげて、リュックサックに入れられるりんごの総価格の最大値を求めます.
入力
複数のテストデータがあり、各テストデータの最初の動作は2つの正の整数で、それぞれアップルの個数nとリュックサックの容量vを表し、n、vが同時に0の場合にテストを終了し、このとき出力しない.次のn行は、行ごとに2つの正の整数で、リンゴの大きさcと価格wをそれぞれ表すスペースで区切られています.すべての入力値の範囲は0以上1000以下です.
しゅつりょく
各テストデータに整数を出力し、リュックサックに入れることができるアップルの総価値を表します.
サンプル入力

3 3
1 1
2 1
3 1
0 0

サンプル出力

2

ソース
ダイナミックプランニングの古典的な問題

          ，   ：        ，        。
        ： f[i][v]   i           v            。          ：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
        ，                         。             ：“  i        v    ”     ，     i      （    ），              i-1      。     i   ，        “ i-1        v    ”，   f[i-1][v]；    i   ，        “ i-1           v-c[i]    ”，            f[i-1][v-c[i]]        i        w[i]。

コード:
#include #include int a[1001][1001]={0},c[1001]={0},w[1001]={0}; int max(int x,int y) { return x>y?x:y; } int maxweight(int n,int v) { int i,j; for(i=1;i<=n;i++) for(j=1;j<=v;j++) { if(j>=c[i]) a[i][j]=max(a[i-1][j],a[i-1][j-c[i]]+w[i]); else a[i][j]=a[i-1][j]; } return a[n][v];    }                int main() { int n,v,maxw,i,j; while(scanf("%d %d",&n,&v)&&(n||v)) { for(i=1;i<=n;i++) scanf("%d %d",&c[i],&w[i]); memset(a,0,sizeof(a));    maxw=maxweight(n,v); printf("%d",maxw);     } return 0; }