Problem of the day
You are given 'N' stones labeled from 1 to 'N'. The 'i-th' stone has the weight W[i]. There are 'M' colors labeled by integers from 1 to 'M'. The 'i-th' stone has the color C[i] which is an integer between 1 to 'M', both inclusive.
You have been required to fill a Knapsack with these stones. The Knapsack can hold a total weight of 'X'.
Write a program to calculate the best way to fill the Knapsack - that is, the unused capacity should be minimized.
The first line contains three integers 'N', 'M', and 'X', separated by a single space. Where 'N' represents the total number of stones, 'M' represents the total number of colour stones, and 'X' represents the total weight of the knapsack.
The second line contains 'N' integers, W[1], W[2], W[3] ..W[i]… W[N], separated by a single space.
The third line contains 'N' integers C[1], C[2], C[3] ..C[i]… C[N], separated by single space.
Output Format:
The output prints the minimum unused capacity of the Knapsack(a single integer). If there is no way to fill the Knapsack, print -1.
1 <= M <= N <= 100
1 <= X <= 10000
1 <= W[i] <= 100
1 <= C[i] <= M
Time Limit: 1 sec
3 3 5
1 1 1
1 2 3
2
We have three stones of each color and hence, we have to select it and in turn, we get a total weight equal to 1 + 1 + 1 = 3. So the minimum unused capacity is 5 - 3 = 2.
8 3 13
2 3 4 2 4 5 2 3
1 1 1 2 2 2 3 3
1
We can choose the stone with:
1. Colour as 1 and with Weight 4,
2. Colour as 2 and with Weight 5, and
3. Colour as 3 and with Weight 3
So we a total weight 4 + 5 + 3 = 12. Hence the minimum unused capacity is 13 - 12 = 1.
We cannot get weight more than 12 with any other combination.
Can you relate this problem to the standard knapsack problem? If you have weights of each colour separated, think of how you would create the recurrence relation.
current weight + weight of this stone <= X
and call the recursive function with the next color (as we can use only one stone of color), and new weight as current weight + weight of this stone.
4. Initialize answer with a minimum value of integer and update the answer with maximum from the recursive calls.
5. In the main function, return -1 if the helper function answer is less than 0, otherwise return (x - helperAnswer).
O(2 ^ N), Where N is the number of stones.
For every stone, we will have 2 options; either add this stone to the knapsack or don’t. For N stone, the overall Time Complexity is O(2 ^ N).
O(N), Where N is the number of stones.
In the worst case, there will be N recursion calls stored in the stack. Hence, the overall Space Complexity is O(N).