DP / Pattern Types0/1 KnapsackMedium

0/1 Knapsack — Include or Exclude Each Item

Given items with weight and value, maximize value within a weight capacity. dp[i][w] = max(skip, take).

GFG
Practice on GeeksforGeeks: 0/1 Knapsack
Open Problem

Knapsack Pattern

For each item, make a binary choice: include it or exclude it. If included, subtract its weight from capacity and add its value. The table is indexed by (item index, remaining capacity).

Recurrence

dp[i][w] = dp[i-1][w] // skip item i
if wt[i] <= w:
  dp[i][w] = max(dp[i][w],
    dp[i-1][w - wt[i]] + val[i]) // take
Interactive Visualization
Computing
Source Cells
Answer
Items
DP Table (rows: items, cols: capacity 0..W)
Step 0 of 0
Item
—
Capacity
—
Decision
—
Max Value
—
Ready. Press Play or Next to start.
✓ Done
Speed
C++ — 0/1 Knapsack
int knapsack(int W, vector<int>& wt, vector<int>& val) {
    int n = wt.size();
    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++) {
            dp[i][w] = dp[i-1][w]; // skip
            if (wt[i-1] <= w)
                dp[i][w] = max(dp[i][w],
                    dp[i-1][w-wt[i-1]] + val[i-1]);
        }
    }
    return dp[n][W];
}
Complexity
Time
O(N × W)

N items, W capacity. Pseudo-polynomial.

Space
O(N × W)

Can optimize to O(W) with 1D array.

📝 Notes

▼