nyoj 289りんご

りんご
時間制限:
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

考え方:この問題は0-1リュックサック問題に属し、この問題をする前に必ず理解しなければならない.状態遷移方程式F[i,v]=max{F[i−1,v],F[i−1,v−Ci]+Wi}という方程式は非常に重要であり、基本的にリュックサックに関連する問題の方程式はすべてそれによって派生している.詳しく説明する必要があります
前のiつの品物を容量vのリュックサックに入れる」という問題がある.i番目のアイテムのポリシー(置くか置かないか)だけを考慮すれば、変換できます.
前i−1件のみに関する問題である.i番目のアイテムを置かないと、問題は「前のi−1アイテムを容量vの背中に入れる
パッケージ中」、価値はF[i−1,v];i番目のアイテムを入れると、問題は「前のi−1アイテムを残りの容量v−Ciのリュックサックに入れる」ことに変わり、このとき得られる最大の価値はF[i−1,v−Ci]に加えてi番目のアイテムを入れることで得られる価値Wiである.また、この問題では、2次元配列を使用する場合は、必ずグローバル変数として定義する必要があります.そうしないと、プログラムが直接クラッシュします.

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[1010][1010];  //        
int main()
{
    int n,v;
    while(~scanf("%d%d",&n,&v))
    {
        if(n==0&&v==0)
            break;
        int i,j;
        int w[1010]= {0},p[1010]= {0};
        memset(dp,0,sizeof(dp));
        for(i=1; i<=n; i++)
            scanf("%d%d",&w[i],&p[i]);
        for(i=1; i<=n; i++)
            for(j=1; j<=v; j++)
                if(w[i]>j)    //         
                    dp[i][j]=dp[i-1][j];//       
                else
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);  //           
        printf("%d
",dp[n][v]);
    }
    return 0;
}