0

我知道如何编写 0-1 背包问题的解决方案。但是，我不知道如何更改此代码，以便我们可以选择同一项目的多个副本。因此，对于每个项目 i ，我们有另一个参数 k(i)，它表示 i 存在的副本数。如果有人可以帮助我，我将不胜感激。下面是我在 k(i) = 1 时的代码。查看背包函数以获得自上而下的 dp 解决方案

#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)

现在，您还需要一个字段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 回答