So I am trying to solve a problem related to unbounded knapsack where we have the liberty of choosing the items as many times as we want but in this variation we can only do it for a fixed number of time say K. I tried using a vector to keep track of how many times I have used an item and whether I can use it again but for some reason I am making a mistake and not getting the correct output. Below is my code and a sample test case.
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int KnapSack(int W, int wt[], int value[], int n, vector<int>& processed)
{
int t[n+1][W+1];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=W;j++)
{
if(i==0 || j==0)
{
t[i][j] = 0;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=W;j++)
{
if(wt[i-1]<=j )
{
if(processed[i-1]>1)
{
t[i][j] = max(value[i-1] + t[i][j-wt[i-1]], t[i-1][j]);
processed[i-1] -= 1;
}
else
{
t[i][j] = max(value[i-1] + t[i-1][j-wt[i-1]], t[i-1][j]);
}
}
else
{
t[i][j] = t[i-1][j];
}
}
}
return t[n][W];
}
int main(){
int n;
cin>>n;
int wt[n];
int value[n];
vector<int> processed(n);
for(int i=0;i<n;i++)
{
processed[i] = 2;
}
for(int i=0;i<n;i++)
{
cin>>wt[i];
}
for(int i=0;i<n;i++)
{
cin>>value[i];
}
int W;
cin>>W;
int ans = KnapSack(W, wt, value, n, processed);
cout<<ans<<endl;
for(int i=0;i<n;i++)
{
cout<<processed[i]<<" "<<endl;
}
return 0;
} ```
Test Case :- wt[] = {20, 10, 30, 40}
value[] = {1, 1, 9, 8 }
max weight = 100
max usage of an item (K) = 2
Now my code gives output as 19 whereas the correct output should be 26 which comes when we use item with weight '30' 2 times and item with weight '40' 1 times so that gives 2*9 + 8 = 26.
Please help!Comments (0)