Модифицированная версия рюкзака

Question

Я знаю, как закодировать решение проблемы с рюкзаком 0-1. Однако я не знаю, как изменить этот код, чтобы мы могли выбрать несколько копий одного и того же элемента. Итак, для каждого элемента i мы имеем еще один параметр k (i), который обозначает количество экземпляров i. Я буду обязан, если кто-то сможет мне помочь. Ниже мой код, когда к (я) = 1. Посмотрите на функции рюкзака для верхнего вниз раствора йра

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

} 

Answer 1

Вашего код ранец является слишком сложным. Вот еще один способ сделать это:

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