public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public int solve(final List A, final List B, final List C) {
int minCost = 0, maxCap = 0;
int n = B.size();
for(int i=0; i<A.size(); i++) {
if(A.get(i)>maxCap) {
maxCap = A.get(i);
}
}
int[][] K = knapsack(maxCap, n, B, C);
for(int i=0; i<A.size(); i++) {
minCost += K[n][A.get(i)];
}
return minCost;
}
private int[][] knapsack(int C, int n, final List<Integer> W, final List<Integer> Cost) {
int[][] K = new int[n+1][C+1];
for(int i=0; i<n; i++) {
/** IMPORTANT - initialise to a value less than MAX, else it can overflow on adding cost in the loop and result in wrong answer due to wrap around feature of Java */
Arrays.fill(K[i], Integer.MAX_VALUE/2);
}
for(int j=0; j<=C; j++) {
for(int i=1; i<=n; i++) {
if (j==0) {
K[i][j] = 0;
} else if(W.get(i-1) <= j) {
K[i][j] = Math.min(K[i-1][j], K[i][j-W.get(i-1)] + Cost.get(i-1));
} else {
K[i][j] = K[i-1][j];
}
}
}
return K;
}
}