# Java Solution using DP

#1

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;
}
``````

}

#2

Great insights in between.Thanks