Unbounded Knapsack (Repetition of items allowed)

The problem, simply

You have a bag that can hold a total weight of W. There are n kinds of items. Each kind has a weight and a value, and the shop never runs out, so you may take any kind as many times as you want. Give back the biggest total value that fits in the bag.

This is the knapsack problem with one change: items can repeat.

A story to remember it

Picture it

Examples

Way 1: the simple way

best(cap) is the most value a bag of size cap can hold.

1. Try every item that fits as the last one in the bag.
2. It is worth its value plus best(cap - weight), the best for the room that is left.
3. Keep the biggest. If nothing fits, the answer is 0.

class Solution {
    public int unboundedKnapsack(int W, int[] weight, int[] value) {
        int best = 0;
        for (int i = 0; i < weight.length; i++) {
            if (weight[i] <= W) {
                // item i goes in last, the rest of the room is solved the same way
                best = Math.max(best, value[i] + unboundedKnapsack(W - weight[i], weight, value));
            }
        }
        return best;
    }
}

How long it takes: each call can branch into all n items and the chain can be W long (with a weight 1 item), so up to O(n^W). Extra room: the call chain, O(W).

Way 2: the clever way

There are only W + 1 bag sizes. Fill a row best[0..W] from small to big. When you reach size c, every smaller size is already known.

1. best[0] = 0.
2. For each size c from 1 to W, for each item that fits: best[c] = max(best[c], best[c - weight] + value).
3. Return best[W].

Because best[c - weight] is allowed to already contain the same item, repeats come for free.

class Solution {
    public int unboundedKnapsack(int W, int[] weight, int[] value) {
        int[] best = new int[W + 1];          // best[0] = 0
        for (int c = 1; c <= W; c++) {
            for (int i = 0; i < weight.length; i++) {
                if (weight[i] <= c) {
                    // item i last, plus the best for the room left
                    best[c] = Math.max(best[c], best[c - weight[i]] + value[i]);
                }
            }
        }
        return best[W];
    }
}

How long it takes: W sizes times n items, O(n * W). Extra room: one row, O(W).

Watch out for

• Greedy by value per weight is wrong, as the [5, 6] example shows.
• If the bag must be filled exactly, start every best[c] at minus infinity (except best[0] = 0), so impossible sizes stay impossible.
• With a huge W (in the billions) the row does not fit. That is a different problem and needs other tricks.

What interviewers ask next

• Does the loop order matter? For the best value, no: items outside and capacity inside (low to high) gives the same answer. For counting ways, yes. Items outside counts combinations (coin change II), capacity outside counts ordered sequences.
• Print which items to take. Keep pick[c], the item that gave the best at size c. Then from W, take pick[W] and jump to W - weight.
• Rod cutting is the same problem: piece lengths are weights, prices are values, the rod length is W.
• Coin change (fewest coins) is the same shape with min and +1 instead of max and +value.

Remember this

Grown-up words: the bag is the knapsack, its size is the capacity W, endless jars mean the unbounded knapsack, the row of best values is 1D dynamic programming, and the 0/1 version is the bounded knapsack.