Colorful Knapsack
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'.

You are required to select exactly 'M' stones; one of each color. The sum of the weights of the stones must not exceed 'X'. Since you paid a premium for a Knapsack with capacity 'X', you are required to fill the Knapsack as much as possible.

Write a program to calculate the best way to fill the Knapsack - that is, the unused capacity should be minimized.

Input format:

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.

Constraints :

1

Question

Colorful Knapsack

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'.

You are required to select exactly 'M' stones; one of each color. The sum of the weights of the stones must not exceed 'X'. Since you paid a premium for a Knapsack with capacity 'X', you are required to fill the Knapsack as much as possible.

Write a program to calculate the best way to fill the Knapsack - that is, the unused capacity should be minimized.

Input format:

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.

Constraints :

1 <= M <= N <= 100
1 <= X <= 10000
1 <= W[i] <= 100
1 <= C[i] <= M

Time Limit: 1 sec

Accepted Answer

Recursive Approach

Create an array/list of size m+1. Let’s call this as weights, and add each weight of i’th color at the index i.
Call a recursive function with color 1 and having current weight as 0. The base case would be If we reach the (m+1)th color means we have exhausted the colors so return 0.
Now for i’th color, we will have a list of stones. We will try using each stone. We will use the stone if the

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

Space Complexity: O(n)Explanation:

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

Time Complexity: O(2^n)Explanation:

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

Accepted Answer

Memoization

Create an array of the vector of size m+1 let’s call it ‘weights’, and add each weight of i’th color at the index i.
Create a 2D integer array of size (M+1)*(X+1). Let’s call this DP. Fill it with -1s.
Call a recursive function with color 1 and having current weight as 0. The base case would be If we reach the m+1’th color means we have exhausted the colors so return 0. If dp[color][currentWeight] is not equal to -1, simply return it. Otherwise, proceed to step 4.
Now for i’th color, we will have a list of stones. We will try using each stone. We will use the stone if the

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.

5. Initialize answer with a minimum value of integer and update the answer with maximum from the recursive calls.

6. In the main function, return -1 if the helper function answer is less than 0, otherwise return (x - helperAnswer).

Space Complexity: OtherExplanation:

O(M * X), where M is the number of colours, and X is the weight of the knapsack.

We are creating a 2-Dimensional array of size M * X. Hence, .the overall Space Complexity is O(M * X).

Time Complexity: OtherExplanation:

O(N * X), where N is the number of stones, and X is the weight of the knapsack.

By checking the code it seems Time complexity is O(N*X*N) as we are having a loop in every state but on closer inspection, we can easily notice that the summation of the product of color and loop will be N. Hence, the overall Time Complexity is O(N * X).

Accepted Answer

Iterative DP

Create an array of the vector of size m+1. Let’s call it weights, and add each weight of i’th color at the index i.
Create a 2D boolean array of size (M+1)*(X+1). Let’s call this DP.
Initialize DP[0][0]=True: as we can always get 0 weight.
Run three loops: first for i’th color (from 1 to M), 2nd loop for j’th weight (from 1 to X), and the third loop to try using each stone of i’th color.
If the weight of one of the stones of the i’th color is W, then if we use this at j’th weight, we will reach the state with one less color and with weight j - W. So, we update the current state using the previous state i.e dp[i][j] |= dp[i - 1][j - W];
If there is no possible way to fill the i'th color i.e entire ith row is false then return -1. As we are not allowed to skip any color.
The maximum weight that can be added to the knapsack will be at the rightmost index of dp[m] which has a True value. So for this run a loop from X to 1, and whenever dp[m][i] == True. Return the unused capacity i.e x - I.
If the answer is still -1, no answer exists. Return -1.

Space Complexity: OtherExplanation:

O(M*X), where M is the number of colours, and X is the weight of the knapsack.

We are creating a 2-Dimensional array of size M * X. Hence, the overall Space Complexity is O(M*X).

Time Complexity: OtherExplanation:

O(N * X), where N is the number of stones, and X is the weight of the knapsack.

By checking the code it seems Time complexity is O(N*X*N) as we are having 3 loops but on closer inspection, we can easily notice that the first loop and last loop will run in total N times and the second loop will run X time. Hence, the overall Time Complexity is O(N * X).