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