Colorful Knapsack

Hard

0/120

Average time to solve is 45m

Contributed by

63 upvotes

+18 more companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

3 3 5
1 1 1
1 2 3

Sample Output 1:

Explanation of Sample Input 1:

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.

Sample Input 2:

8 3 13
2 3 4 2 4 5 2 3
1 1 1 2 2 2 3 3

Sample Output 2:

Explanation of Sample Input 2:

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.

Console