0

0-1 ナップザック問題の解決策をコーディングする方法を知っています。ただし、同じアイテムの複数のコピーを選択できるようにこのコードを変更する方法がわかりません。したがって、各アイテム i に対して、存在する i のコピー数を示す別のパラメーター k(i) があります。誰かがこれで私を助けることができれば、私は義務付けられます. 以下は、k(i) = 1 の場合の私のコードです。トップダウン dp ソリューションの knapsack 関数を見てください。

#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int n, g;
int p[1005],w[1005];
int dp[1004][35];// num of object and weight left

int knapsack(int resourcel, int item){
    //if(resourcel < 0) return (1<<31);
    if(item == n) return 0;
    if(resourcel == 0) return 0;
    if(dp[item][resourcel] != -1) return dp[item][resourcel];

    if(resourcel - w[item] < 0){
        dp[item][resourcel]  = knapsack(resourcel,item+1);
        return dp[item][resourcel];
    }
    else{
        int take = knapsack(resourcel - w[item],item+1) + p[item];
        int notTake = knapsack(resourcel,item+1);
        dp[item][resourcel] = take > notTake?take : notTake;
        return dp[item][resourcel];
    }


}
int main(){
    int tc,dummy, sum =0;
    //freopen("in.txt","r",stdin);
    scanf("%d",&tc);
    for(int i = 0 ; i < tc; i++){
        sum  = 0;
        memset(dp,-1,sizeof(dp));
        scanf("%d",&n);
        //cout<<" n is : "<<n<<endl;
        for(int j = 0 ; j < n ;j++){
            scanf("%d %d",&p[j],&w[j]);
            //cout<<" price and val  is : "<<p[j]<<" " << w[j]<<endl;
        }
        scanf("%d",&g);
        //cout<<"g is : "<<g<<endl;
        for(int p = 0 ; p< g;p++){
            scanf("%d",&dummy);
            sum+= knapsack(dummy,0);//wight allowed and item visited
        }
        printf("%d\n",sum);

    }

    return 0;

}
4

1 に答える 1

0

あなたのナップザック コードは非常に複雑です。これを行う別の方法を次に示します。

しましょうdp[i] = maximum profit we can get for weight i。

for i = 1 to numItems do
  for j = knapsackWeight down to items[i].weight do
    dp[j] = max(dp[j], dp[j - items[i].weight] + items[i].profit)

ここで、 field も必要ですitem.copies。途中に別のループを追加するだけで、これを何度も繰り返すことができます。

for i = 1 to numItems do
  for k = 1 to items[i].copies do
    for j = knapsackWeight down to items[i].weight do
      dp[j] = max(dp[j], dp[j - items[i].weight] + items[i].profit)
于 2013-02-12T11:17:20.437 に答える