nyoj 311完全リュックサック

1673 ワード
完全リュックサック
時間制限:
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を出力します).
サンプル入力
2
1 5
2 2
2 5
2 2
5 1

サンプル出力
NO
1

完全バックパックのテンプレート:
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#define INF 0x3f3f3f
using namespace std;
int c[2010],w[2010];
int dp[100010];
int main()
{
    int t,n,M,V;
    int k,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&M,&V);
        for(i=0;i<M;i++)
        {
            scanf("%d%d",&c[i],&w[i]);
        }
        memset(dp,-INF,sizeof(dp));
        dp[0]=0;
        for(i=0;i<M;i++)
        {
            for(j=c[i];j<=V;j++)
            {
                dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
            }
        }
        if(dp[V]>0)
        printf("%d
",dp[V]);
        else
        printf("NO
");
    }
    return 0;
}

 
homebrewで移行先macへ簡単にアプリを移動させる
Ubuntu下nginx,php,mysqlとgolangの簡単なインストール