Thoroughly explained simple Java solution


#1

Credit to @subhajit-manna_314 for the idea, I converted his solution from C++ to Java.

Explanation
  • Prerequisite - understand how the 0/1 knapsack problem is solved. I found this YouTube video helpful (https://www.youtube.com/watch?v=xCbYmUPvc2Q). Note as you’re watching it how you could also use a 1-D array (of a row) and overwrite values while comparing maximums of the computed value and the existing value (see the second solution at https://www.geeksforgeeks.org/space-optimized-dp-solution-0-1-knapsack-problem/).
  • As the hint notes, the first step is to notice how the friends can each be thought of as knapsacks. We don’t want to rebuild a table for each friend though, so we find the max eating capacity of the friends and use that (plus 1) to dictate the length of the array.
  • The other two things that make this problem different than the classic 0/1 knapsack problem is (A) that we are focusing on minimum cost and not maximum (profit for example) and (B) that it’s unbounded (we can take (whole) items unlimited times as long as we stay at or under capacity).
  • We initialize the array, which defaults to 0’s in Java, then, to deal with (A) as noted above, fill everything but the first column with a very large number (to represent the fact that we can’t yet meet the current eating capacity with the dishes we’ve encountered thus far). We use MAX_VALUE / 2 and not MAX_VALUE because we want to be able to add to it without having an overflow.
  • Calculate, for each dish at each capacity that it can satisfy up to and including max capacity of our table, the minimum cost between taking and not taking the dish. The “up to and including” is driven by the inner for loop (cap = curDishFillCap; cap < dpTable.length). Using a 1D array still allows us to know the “previous” (cost if curr dish not taken) solution that we use to compare for min cost with the current cost (cost if curr dish taken). To deal with (B) noted above we use a slightly different calculation from the classic 0/1 knapsack problem calculation as seen in the code.
  • Lastly, iterate through the list of friends eating capacities and use our dpTable to accumulate the minTotalCost of all friends combined.

Code (suggestions welcome via Reply):

public static int solve(final List < Integer > friendsEatCaps, final List < Integer > dishesFillCaps,
    final List < Integer > dishesCosts) {
    int minTotalCost = 0;
    if (friendsEatCaps != null && dishesFillCaps != null && dishesCosts != null && friendsEatCaps.size() > 0 &&
        dishesFillCaps.size() == dishesCosts.size()) {
        int friendsMaxEatCap = Collections.max(friendsEatCaps);
        int[] dpTable = new int[friendsMaxEatCap + 1]; // initialize with 0s, only [0] will remain as 0
        Arrays.fill(dpTable, 1, dpTable.length, Integer.MAX_VALUE / 2); // div MAX_VALUE by 2 to avoid overflow
        for (int dishIdx = 0; dishIdx < dishesFillCaps.size(); dishIdx++) {
            int curDishFillCap = dishesFillCaps.get(dishIdx);
            int curDishCost = dishesCosts.get(dishIdx);
            for (int cap = curDishFillCap; cap < dpTable.length; cap++) { // start with cap the dish can fill
                int costIfDishTaken = dpTable[cap - curDishFillCap] + curDishCost; // where we avoid overflow
                dpTable[cap] = Math.min(costIfDishTaken, dpTable[cap]);
            }
        }
        for (int friendEatCap: friendsEatCaps) {
            minTotalCost += dpTable[friendEatCap]; // for each friend accumulate min cost
        }
    }
    return minTotalCost;
}

#2

Are you God?-------------------


#3

bhai yar code likhna sikh le kachra likha ha tuna aisa likhaga na khi interview me ati hongi bhi chiza to bhaga degh