New update is available. Click here to update.

Topics

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.

Detailed explanation

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