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] (of course, an integer between 1 to M, inclusive). You want to fill a Knapsack with these stones. The Knapsack can hold a total weight of X. You want 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 (as opposed to a Knapsack with a lower capacity), you want to fill the Knapsack as much as possible.↵
↵
Write a program that takes all the above values as input and calculates the best way to fill the Knapsack – that is, the way that minimizes the unused capacity. Output this unused capacity. See the explanation of the sample test cases for clarity.↵
↵
Input↵
The first line of input contains the integer T, the number of test cases. Then follows the description of T test cases. The first line of each test case contains three integers, N, M and X, separated by singlespace. The next line contains N integers, W[1], W[2], W[3] … W[N], separated by single space. The next line contains N integers C[1], C[2], C[3] … C[N], separated by single space.↵
↵
Output↵
An optimal way of filling the Knapsack minimizes unused capacity. There may be several optimal ways of filling the Knapsack. Output the unused capacity of the Knapsack (a single integer on a line by itself) for an optimal way. If there is no way to fill the Knapsack, output -1. Output T lines, one for each test case.↵
↵
Constraints↵
1 ≤ T ≤ 10↵
1 ≤ M ≤ 100↵
M ≤ N ≤ 100↵
1 ≤ W[i] ≤ 100↵
1 ≤ C[i] ≤ M↵
1 ≤ X ≤ 10000↵
↵
Sample Input↵
4↵
↵
9 3 10↵
↵
2 3 4 2 3 4 2 3 4↵
↵
1 1 1 2 2 2 3 3 3↵
↵
9 3 10↵
↵
1 3 5 1 3 5 1 3 5↵
↵
1 1 1 2 2 2 3 3 3↵
↵
3 3 10↵
↵
3 4 4↵
↵
1 2 3↵
↵
3 3 10↵
↵
3 3 3↵
↵
1 2 1↵
↵
Sample Output↵
0↵
↵
1↵
-1↵
-1↵
↵
-1↵
↵
Is this possible using only two states dp? I think it might need three states- for ith element, color c, and knapsack capacity X.
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] (of course, an integer between 1 to M, inclusive). You want to fill a Knapsack with these stones. The Knapsack can hold a total weight of X. You want 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 (as opposed to a Knapsack with a lower capacity), you want to fill the Knapsack as much as possible.↵
↵
Write a program that takes all the above values as input and calculates the best way to fill the Knapsack – that is, the way that minimizes the unused capacity. Output this unused capacity. See the explanation of the sample test cases for clarity.↵
↵
Input↵
The first line of input contains the integer T, the number of test cases. Then follows the description of T test cases. The first line of each test case contains three integers, N, M and X, separated by singlespace. The next line contains N integers, W[1], W[2], W[3] … W[N], separated by single space. The next line contains N integers C[1], C[2], C[3] … C[N], separated by single space.↵
↵
Output↵
An optimal way of filling the Knapsack minimizes unused capacity. There may be several optimal ways of filling the Knapsack. Output the unused capacity of the Knapsack (a single integer on a line by itself) for an optimal way. If there is no way to fill the Knapsack, output -1. Output T lines, one for each test case.↵
↵
Constraints↵
1 ≤ T ≤ 10↵
1 ≤ M ≤ 100↵
M ≤ N ≤ 100↵
1 ≤ W[i] ≤ 100↵
1 ≤ C[i] ≤ M↵
1 ≤ X ≤ 10000↵
↵
Sample Input↵
4↵
↵
9 3 10↵
↵
2 3 4 2 3 4 2 3 4↵
↵
1 1 1 2 2 2 3 3 3↵
↵
9 3 10↵
↵
1 3 5 1 3 5 1 3 5↵
↵
1 1 1 2 2 2 3 3 3↵
↵
3 3 10↵
↵
3 4 4↵
↵
1 2 3↵
↵
3 3 10↵
↵
3 3 3↵
↵
1 2 1↵
↵
Sample Output↵
0↵
↵
1↵
-1↵
↵
-1↵
↵
Is this possible using only two states dp? I think it might need three states- for ith element, color c, and knapsack capacity X.
