# Colorful Knapsack

Posted: 17 Jul, 2020
Difficulty: Hard

## PROBLEM STATEMENT

#### 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, W, W ..W[i]… W[N], separated by a single space.

The third line contains 'N' integers C, C, C ..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
`````` Approach 1
1. 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.
2. 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.
3. 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).