0/1 knapsack

Choose items with weights and values to maximise total value without exceeding a weight limit. Each item is used at most once.

Time O(n × capacity)Space O(n × capacity)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

dp[i, c] is the best value using the first i items with capacity c. For each item either skip it (the cell above) or take it (its value plus the best for the remaining capacity, from the row above).

Code

C++PythonC#

int knapsack(const vector<int>& wt, const vector<int>& val, int cap) {
    int n = (int)wt.size();
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int c = 0; c <= cap; c++) {
            dp[i][c] = dp[i - 1][c];
            if (wt[i - 1] <= c)
                dp[i][c] = max(dp[i][c],
                    dp[i - 1][c - wt[i - 1]] + val[i - 1]);
        }
    return dp[n][cap];
}

def knapsack(wt: list[int], val: list[int], cap: int) -> int:
    dp = [[0] * (cap + 1) for _ in range(len(wt) + 1)]
    for i in range(1, len(wt) + 1):
        for c in range(cap + 1):
            dp[i][c] = dp[i - 1][c]
            if wt[i - 1] <= c:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - wt[i - 1]] + val[i - 1])
    return dp[len(wt)][cap]

public static int Knapsack(int[] wt, int[] val, int cap) {
    var dp = new int[wt.Length + 1, cap + 1];
    for (int i = 1; i <= wt.Length; i++)
        for (int c = 0; c <= cap; c++) {
            dp[i, c] = dp[i - 1, c];
            if (wt[i - 1] <= c)
                dp[i, c] = Math.Max(dp[i, c],
                    dp[i - 1, c - wt[i - 1]] + val[i - 1]);
        }
    return dp[wt.Length, cap];
}

Tips

Both options read from the row above, which is what stops an item being used twice.
Each row only needs the previous one, so a single array filled right to left is enough.

In the .NET library

Parallel arrays wt and val are the usual interview signature. In production code a record struct Item(int Weight, int Value) reads better.