0/1 Knapsack — Dynamic Programming
Watch the DP matrix fill row by row. For each cell dp[i][w], the algorithm evaluates two choices — skip or take item i — and picks the maximum. Traceback then recovers the exact items selected.
Problem Preset
Playback
Legend
DP Matrix — dp[0..4][0..7]
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
capacity → | ||||||||
dp[0] — no items | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Item 1w=1 v=1 | 0 | ? | ? | ? | ? | ? | ? | ? |
Item 2w=3 v=4 | 0 | ? | ? | ? | ? | ? | ? | ? |
Item 3w=4 v=5 | 0 | ? | ? | ? | ? | ? | ? | ? |
Item 4w=2 v=3 | 0 | ? | ? | ? | ? | ? | ? | ? |
dp[i][0] = 0 and dp[0][w] = 0 — all cells in row 0 and column 0 are zero.Base cases set: dp[i][0] = 0 (zero capacity) and dp[0][w] = 0 (no items available)
Items (n = 4)
dp[i][w] = dp[i-1][w] if w_i > wdp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i]+v_i)dp[0][w] = 0 (no items)dp[i][0] = 0 (zero capacity)dp[4][7] = ?Reference implementation of 0/1 Knapsack — Dynamic Programming. Select a language tab to view and copy the code.
#include <stdio.h>
#include <string.h>
#define MAX_N 100
#define MAX_W 1000
int max(int a, int b) { return a > b ? a : b; }
int dp[MAX_N + 1][MAX_W + 1];
int knapsack(int n, int W, int weights[], int values[]) {
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
/* Skip item i */
dp[i][w] = dp[i - 1][w];
/* Take item i — only if it fits */
if (weights[i - 1] <= w) {
int take = dp[i - 1][w - weights[i - 1]] + values[i - 1];
dp[i][w] = max(dp[i][w], take);
}
}
}
return dp[n][W];
}
int main() {
int weights[] = {2, 3, 4, 5};
int values[] = {3, 4, 5, 6};
int n = 4, W = 8;
printf("Max value: %d\n", knapsack(n, W, weights, values));
return 0;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int knapsack(int n, int W,
const vector<int>& weights,
const vector<int>& values) {
// dp[i][w] = max value using first i items, capacity w
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
// Option 1: skip item i
dp[i][w] = dp[i - 1][w];
// Option 2: take item i (if it fits)
if (weights[i - 1] <= w) {
int take = dp[i - 1][w - weights[i - 1]] + values[i - 1];
dp[i][w] = max(dp[i][w], take);
}
}
}
return dp[n][W];
}
int main() {
vector<int> weights = {2, 3, 4, 5};
vector<int> values = {3, 4, 5, 6};
int n = 4, W = 8;
cout << "Max value: " << knapsack(n, W, weights, values) << "\n";
return 0;
}import java.util.Arrays;
public class Knapsack01 {
public static int knapsack(int n, int W, int[] weights, int[] values) {
// dp[i][w] = max value with first i items and capacity w
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
// Skip item i
dp[i][w] = dp[i - 1][w];
// Take item i — if it fits
if (weights[i - 1] <= w) {
int take = dp[i - 1][w - weights[i - 1]] + values[i - 1];
dp[i][w] = Math.max(dp[i][w], take);
}
}
}
return dp[n][W];
}
public static void main(String[] args) {
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int n = 4, W = 8;
System.out.println("Max value: " + knapsack(n, W, weights, values));
}
}def knapsack(n: int, W: int,
weights: list[int], values: list[int]) -> int:
# dp[i][w] = max value using first i items with capacity w
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
# Skip item i
dp[i][w] = dp[i - 1][w]
# Take item i — only if it fits
if weights[i - 1] <= w:
take = dp[i - 1][w - weights[i - 1]] + values[i - 1]
dp[i][w] = max(dp[i][w], take)
return dp[n][W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack(4, 8, weights, values)) # 10function knapsack(n, W, weights, values) {
// dp[i][w] = max value using first i items, capacity w
const dp = Array.from({ length: n + 1 },
() => new Array(W + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= W; w++) {
// Skip item i
dp[i][w] = dp[i - 1][w];
// Take item i — if it fits
if (weights[i - 1] <= w) {
const take = dp[i - 1][w - weights[i - 1]] + values[i - 1];
dp[i][w] = Math.max(dp[i][w], take);
}
}
}
return dp[n][W];
}
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
console.log(knapsack(4, 8, weights, values)); // 10Python — Code Walkthrough
Create the 2-D list with list comprehension
dp = [[0] * (W + 1) for _ in range(n + 1)]The list comprehension creates n+1 independent rows of W+1 zeros. Using [0]*(W+1) directly in range(n+1) without comprehension would create n+1 references to the same list — a common Python pitfall.
Skip first, then conditionally take
dp[i][w] = dp[i - 1][w] if weights[i - 1] <= w: take = dp[i-1][w-weights[i-1]] + values[i-1] dp[i][w] = max(dp[i][w], take)Python's max() works identically to C's max macro here. The if guard ensures we never access a negative index (which Python allows but would give wrong results here).
Return the bottom-right corner
return dp[n][W]dp[n][W] is the answer — maximum value achievable with all n items and full capacity W. Python integers are arbitrary-precision, so there is no overflow concern regardless of item values.
Space-efficient 1-D version
dp = [0] * (W + 1) for i in range(n): for w in range(W, weights[i] - 1, -1): dp[w] = max(dp[w], dp[w - weights[i]] + values[i])Iterating w from W down to weights[i] processes each item at most once (0/1 constraint). The range uses weights[i]-1 as the stop so w >= weights[i] is always maintained. This drops space from O(n*W) to O(W).
Why this is pseudo-polynomial
The O(n × W) complexity appears polynomial in n and W, but W is the numeric value of the input — not its bit-length. For W = 2^30, the DP table becomes infeasible. This makes 0/1 Knapsack NP-hard in general, though DP is practical for reasonable W.