Knapsack with Duplicate Items
Weights and values are given for n items along with the maximum capacity allowed W. What is the maximum value we can achieve if we can pick any weights, any number of times for the total allowed capacity of W?
Input:
First line contains two integers N and W denoting the number of items and the total allowed weight.
In the next two lines are space separated values of the array denoting values of the items val[n] and their weights weights[n] respectively.
Output:
Output the maximum value which we can achieve if we can pick any weights any number of times for a total weight capacity of W.
Constraints:
1 <= N,W <= 100
1 <= weight[i], val[i] <= 100
Example:
Test case: 1
Input:
N=2,W= 3
val[]=1 1
weight[]=2 1
Output:
Maximum value that can be achieved: 3
Test case: 2
Input:
N=3,W= 4
val[]=2 5 3
weight[]=1 2 1
Output:
Maximum value that can be achieved: 12
Explanation:
For the first test case,
Will use the second item with weight 1 only.
We use will 3 such item to have maximum value 3.
Any other combinations will give less value
For the second test case,
Some possible combinations can be
Writing as (value, weight) pair
(2,1), (2,1), (2,1), (2,1)- total weight 4, value 8
(2,1), (2,1), (5,2) - total weight 4, value 9
...
(3,1),(3,1), (3,1),(3,1)- total weight 4, value 12
The last combination is the most optimal one
and that's produces the maximum.
The difference between this problem and the general knapsack problem is here we can use the same item several times. So the simple recursion about either choosing an item or leaving the item will not work here as using the same item may lead to the most optimized solution.
Hence, the algorithm will be like following,
memset(dp,0,sizeof(dp));
Let's compute the above for our test case two,
Initially the DP table is,
To compute dp[1],
Similar way you can hand compute the DP table to understand how the algo is performing is reaching to the optimal answer.
The final DP table for the above test case would look like,
Where 12 is the final case.
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer