Knapsack Problem

The problem, simply

You have n things. Each one has a weight and a value. Your bag can carry at most W weight. Pick some things so the total weight is at most W and the total value is as big as possible. You cannot cut a thing in half, and you cannot take the same thing twice.

Give back the biggest total value. This is the 0/1 knapsack problem: for each thing, 0 means leave it, 1 means take it.

A story to remember it

Picture it

Examples

Way 1: the simple way

Look at the last toy. There are only two choices.

1. If there are no toys left or no room left, the fun is 0.
2. If the toy is heavier than the room left, you must skip it.
3. Otherwise try both: skip it, or take it (add its value and lose its weight). Keep the better one.

Each toy doubles the number of choices, and different choices often land on the same question, like "2 toys left and 4 kg of room".

class Solution {
    // i = how many toys we still consider, room = weight we can still carry
    public int best(int[] wt, int[] val, int i, int room) {
        if (i == 0 || room == 0) return 0;                    // no toys or no room
        if (wt[i - 1] > room) return best(wt, val, i - 1, room); // too heavy, skip
        int skip = best(wt, val, i - 1, room);
        int take = val[i - 1] + best(wt, val, i - 1, room - wt[i - 1]);
        return Math.max(skip, take);
    }

    public int knapsack(int[] wt, int[] val, int W) {
        return best(wt, val, wt.length, W);
    }
}

How long it takes: each toy splits the work in two, O(2^n). Extra room: the chain of waiting calls is at most n deep, O(n).

Way 2: the clever way

The question "best fun with the first i toys and a bag of size c" only has (n + 1) * (W + 1) versions. Answer each one once in a table, called dp.

1. Row 0 (no toys) and column 0 (no room) are all 0.
2. For toy i and bag size c, first copy the box above: that is "leave toy i".
3. If toy i fits, also try "take it": its value plus the box in the row above at column c - weight. Keep the bigger.
4. The bottom right box dp[n][W] is the answer.

class Solution {
    public int knapsack(int[] wt, int[] val, int W) {
        int n = wt.length;
        int[][] dp = new int[n + 1][W + 1];   // row 0 and column 0 stay 0

        for (int i = 1; i <= n; i++) {
            for (int c = 0; c <= W; c++) {
                dp[i][c] = dp[i - 1][c];                            // leave toy i
                if (wt[i - 1] <= c) {                               // toy i fits
                    dp[i][c] = Math.max(dp[i][c],
                            val[i - 1] + dp[i - 1][c - wt[i - 1]]); // take toy i
                }
            }
        }
        return dp[n][W];
    }

    // Same answer with one row. Go from big bags to small ones,
    // so every toy is used at most once.
    public int knapsackOneRow(int[] wt, int[] val, int W) {
        int[] dp = new int[W + 1];
        for (int i = 0; i < wt.length; i++) {
            for (int c = W; c >= wt[i]; c--) {
                dp[c] = Math.max(dp[c], val[i] + dp[c - wt[i]]);
            }
        }
        return dp[W];
    }
}

How long it takes: one quick step per box, O(n * W). Extra room: the table, O(n * W), or O(W) with the one row version. Note that W is a number, not a count of things, so a huge W makes this slow. That is why knapsack is called pseudo-polynomial.

Watch out for

• Greedy by biggest value or by best value per kg is not safe for 0/1 knapsack. It only works for the fractional version, where you may cut things.
• Index slips: toy i in the table is wt[i - 1] and val[i - 1] in the arrays.
• W = 0 or no items: the answer is 0, and the loops must not read dp[-1].
• A memo table for the recursion needs -1 as "not solved yet", since 0 is a real answer.

What interviewers ask next

• Which toys did you take? Walk up from the bottom right box. If a box differs from the box above it, that toy was taken; move left by its weight.
• What if each toy can be taken many times? Unbounded knapsack: use one row and loop c upward, or use dp[i][c - w] instead of dp[i - 1][c - w].
• What if W is huge but values are small? Flip the table: for each total value, store the smallest weight that reaches it. That costs O(n * total value).
• Can you split items into two equal halves? That is subset sum, a knapsack where value equals weight and you ask if sum / 2 is reachable.
• What if n is about 40 and W is huge? Meet in the middle: list all subsets of each half (about a million each), sort one side, and match with binary search.

Remember this

Grown-up words: the backpack is the knapsack, fun points are values, the chart is the DP table, the take or leave choice is the 0/1 decision, and the one row trick is space optimization with a reverse loop.