Minimum cost to fill given weight in a bag

The problem, simply

You get a price list cost of length n and a bag size W in kilograms. cost[i] is the price of one packet that weighs i + 1 kg. A price of -1 means that packet size is sold out. The shop has as many packets of each size as you want.

Fill the bag to exactly W kg for the least money. If it cannot be done exactly, give back -1.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every packet as the last one in the bag, and solve the smaller bag that is left.

1. f(0) = 0: an empty bag is free.
2. For each available packet of weight s <= w, try cost[s - 1] + f(w - s), but only if f(w - s) is possible.
3. f(w) is the cheapest of those, or "impossible" if none works.

class Solution {
    public int minimumCost(int[] cost, int W) {
        if (W == 0) return 0;                       // empty bag is free
        int best = Integer.MAX_VALUE;
        for (int i = 0; i < cost.length; i++) {
            int size = i + 1;
            if (cost[i] == -1 || size > W) continue;      // sold out or too heavy
            int rest = minimumCost(cost, W - size);
            if (rest != -1) best = Math.min(best, cost[i] + rest);
        }
        return best == Integer.MAX_VALUE ? -1 : best;
    }
}

How long it takes: up to n choices at each of up to W levels, O(n^W). Extra room: the waiting calls, O(W).

Way 2: the clever way

There are only W + 1 different bag sizes. Work out each one once, from light to heavy, in a row dp.

1. dp[0] = 0. Every other box starts at "infinity", which means not possible yet.
2. For each weight w from 1 to W, and each available packet size s <= w: if dp[w - s] is possible, try dp[w - s] + cost[s - 1].
3. The answer is dp[W], or -1 if it is still infinity.

The arrows point from the lighter bags each box builds on.

When some sizes are missing, some bags can never be filled:

import java.util.Arrays;

class Solution {
    public int minimumCost(int[] cost, int W) {
        final int INF = Integer.MAX_VALUE;
        int[] dp = new int[W + 1];
        Arrays.fill(dp, INF);                      // not possible yet
        dp[0] = 0;
        for (int w = 1; w <= W; w++) {
            for (int i = 0; i < cost.length; i++) {
                int size = i + 1;
                if (cost[i] == -1 || size > w || dp[w - size] == INF) continue;
                dp[w] = Math.min(dp[w], dp[w - size] + cost[i]);   // last packet is this size
            }
        }
        return dp[W] == INF ? -1 : dp[W];
    }
}

How long it takes: W weights times n packet sizes, O(n * W). Extra room: one row of W + 1 boxes, O(W).

Watch out for

• Sold out sizes are marked with -1. Do not treat -1 as a price of minus one.
• The bag must be filled exactly. A cheaper way that goes over W does not count.
• This is the unbounded kind: one size can be used many times. That is why the loop over weights is on the outside and each box may reuse any packet.

What interviewers ask next

• What if each packet can be bought only once? Then it is 0/1 knapsack: loop over packets on the outside and weights from high to low.
• How many packets of each size? Keep a choice[w] array of the size used for each box and walk back from W.
• What if W is huge, like a billion? Find the packet with the best price per kg, size b. A best answer uses fewer than b packets of other sizes (otherwise some of them add up to a multiple of b and can be swapped for cheaper b packets). So fill most of the bag with size b and run the small table only on the last few kilograms.
• How is this like coin change? It is the same table: coins are packet sizes, and instead of counting coins you add their prices.

Remember this

Grown-up words: the cheat sheet is a 1D DP table, buying any packet as often as you like is the unbounded knapsack, "infinity" marks an unreachable state, and the repeated f(w) calls are overlapping subproblems.