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

ソース
ダイナミックプランニングの古典的な問題
アップロード者
ctest
動的計画の問題は、主に各ステータスを保存します.
1、最も簡単なのは1つの2次元配列price[j][i]を定義してリュックサックがjであることを表し、前のi個のリンゴの時の最大価値は、それぞれ1~n個目のリンゴに対して計算し、i個目に対して、異なる容量の下の最大値をリストして、後の使用のために、n個目のリンゴを計算し終わるまで、最後にprice[v][n]を得る.
2、リュックの容積が既知であるため、1つの配列で異なる容積で得られた最大価値を表し、1番目のリンゴについては容積が1~vのときの最大値を算出し、2番目のリンゴについても1~vのときの最大価値をn番目のリンゴを算出し、最後にprice[v]を得ることができる.
1つ目の方法:

#include
#include
#include
#include
using namespace std;
int price[1001][1001];
int main()
{
    int n,v,c,w;
    while(scanf("%d%d",&n,&v)==2,n+v)
    {
        memset(price,0,sizeof(price));
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&c,&w);
            for(int j=v;j>=1;j--)
            {
                if(j

2つ目の方法:

#include
#include
#include
#include

using namespace std;
int price[1001];
int main()
{
    int n,v,c,w;
    while(scanf("%d%d",&n,&v)==2,n+v)
    {
        memset(price,0,sizeof(price));
        for(int i=1;i<=n;i++)
        {
            cin>>c>>w;
            for(int j=v;j>=c;j--)
            {
                price[j] = max(price[j],price[j-c] + w);
            }
        }
        cout<