0 1 Knapsack Problem in DSA C++

Mental Model

We want to pick items with weights and values to maximize value without exceeding a weight limit. Each item can be chosen only once.

Analogy: Imagine packing a backpack for a trip. You have limited space (weight limit) and many items with different sizes and usefulness (value). You want to pack the most useful items without overloading the backpack.

Items: [weight: 2, value: 3], [weight: 3, value: 4], [weight: 4, value: 5]
Knapsack capacity: 5
Backpack capacity -> 5
Items -> [2,3], [3,4], [4,5]
Goal: max value ≤ 5 weight

Dry Run Walkthrough

Input: items: weights = [2, 3, 4], values = [3, 4, 5], capacity = 5

Goal: Find the maximum value we can carry without exceeding weight 5, choosing each item at most once.

Step 1: Start with no items, capacity 0 to 5, max value is 0

DP table row 0 (no items): [0, 0, 0, 0, 0, 0]

Why: Base case: no items means no value regardless of capacity

Step 2: Consider item 1 (weight 2, value 3), update DP for capacities 0 to 5

DP row 1: [0, 0, 3, 3, 3, 3]

Why: For capacity ≥ 2, we can take item 1 and get value 3

Step 3: Consider item 2 (weight 3, value 4), update DP for capacities 0 to 5

DP row 2: [0, 0, 3, 4, 4, 7]

Why: At capacity 5, taking items 1 and 2 gives value 7 (3+4)

Step 4: Consider item 3 (weight 4, value 5), update DP for capacities 0 to 5

DP row 3: [0, 0, 3, 4, 5, 7]

Why: At capacity 5, best is still 7 by taking items 1 and 2, item 3 alone gives 5

Result:

Maximum value = 7 at capacity 5 by choosing items 1 and 2

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int knapsack01(const vector<int>& weights, const vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][capacity];
}

int main() {
    vector<int> weights = {2, 3, 4};
    vector<int> values = {3, 4, 5};
    int capacity = 5;

    int max_value = knapsack01(weights, values, capacity);
    cout << "Maximum value = " << max_value << endl;
    return 0;
}

for (int i = 1; i <= n; i++) {

iterate over items to consider each one

for (int w = 0; w <= capacity; w++) {

iterate over all capacities from 0 to max

if (weights[i - 1] <= w) {

check if current item fits in current capacity

dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);

choose max between skipping or taking current item

else { dp[i][w] = dp[i - 1][w]; }

if item doesn't fit, carry forward previous max value

Output

Maximum value = 7

Complexity Analysis

Time: O(n * capacity) because we fill a table with n items and capacity columns

Space: O(n * capacity) due to the 2D DP table storing results for each item and capacity

vs Alternative: Naive approach tries all subsets with exponential time O(2^n), DP reduces it to polynomial time

Edge Cases

empty items list

returns 0 because no items to choose

DSA C++

int n = weights.size();

capacity zero

returns 0 because no capacity to carry items

DSA C++

for (int w = 0; w <= capacity; w++) {

items heavier than capacity

items are skipped, result is 0 or max of lighter items

DSA C++

if (weights[i - 1] <= w) {

When to Use This Pattern

When you see a problem asking to maximize value with weight limits and each item can be chosen once, reach for 0 1 Knapsack DP pattern because it efficiently explores all combinations.

Common Mistakes

Mistake: Using the same item multiple times (unbounded knapsack) instead of once
Fix: Ensure DP transitions consider previous item row, not current, to avoid reuse

Mistake: Not initializing DP base cases properly
Fix: Initialize dp[0][w] = 0 for all w to represent no items chosen

Summary

Finds the max total value of items fitting in a weight limit, choosing each item once.

Use when you must select items with weight constraints and no repeats.

The key is building a table that stores best values for subproblems of items and capacities.

Practice

1. What does the 0 1 Knapsack Problem aim to maximize given a set of items with weights and values?

easy

A. The total weight of items without exceeding the value limit

B. The total value of items without exceeding the weight limit

C. The number of items selected regardless of weight

D. The minimum weight of items selected

Solution

1. Step 1: Understand the problem goal

   The 0 1 Knapsack Problem tries to select items to maximize total value without exceeding the weight capacity.

2. Step 2: Identify the constraint

   The total weight of selected items must not exceed the given weight limit.

3. Final Answer:

   The total value of items without exceeding the weight limit -> Option B

4. Quick Check:

   Maximize value with weight limit = A [OK]

Hint: Maximize value, keep total weight ≤ capacity [OK]

Common Mistakes:

• Confusing weight limit with value limit
• Trying to maximize weight instead of value
• Ignoring the weight constraint

2. Which of the following is the correct way to declare the DP table for the 0 1 Knapsack Problem in C++ if n is number of items and W is max weight?

easy

A. int dp[n+1][W+1];

B. int dp[W+1][n+1];

C. int dp[n][W];

D. int dp[W][n];

Solution

1. Step 1: Understand DP table dimensions

   The DP table stores solutions for items 0 to n and weights 0 to W, so size is (n+1) x (W+1).

2. Step 2: Match correct declaration

   int dp[n+1][W+1]; declares dp with dimensions [n+1][W+1], matching the problem requirements.

3. Final Answer:

   int dp[n+1][W+1]; -> Option A

4. Quick Check:

   DP table size = (n+1) x (W+1) [OK]

Hint: DP table size = items+1 by weight+1 [OK]

Common Mistakes:

• Using dp[n][W] misses base case row/column
• Swapping dimensions incorrectly
• Declaring smaller arrays causing out-of-bound errors

3. What is the output of the following C++ code snippet for 0 1 Knapsack Problem?

int values[] = {60, 100, 120};
int weights[] = {10, 20, 30};
int W = 50;
int n = 3;

int dp[4][51] = {0};

for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= W; w++) {
        if (weights[i-1] <= w) {
            dp[i][w] = std::max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
        } else {
            dp[i][w] = dp[i-1][w];
        }
    }
}

std::cout << dp[n][W] << std::endl;

medium

A. 160

B. 180

C. 220

D. 250

Solution

1. Step 1: Understand the DP logic

   The code fills dp table to find max value for weight limit 50 with items of given weights and values.

2. Step 2: Calculate max value manually

   Items: (10,60), (20,100), (30,120). Max value for weight 50 is choosing items 2 and 3: 100 + 120 = 220.

3. Final Answer:

   220 -> Option C

4. Quick Check:

   Max value for W=50 = 220 [OK]

Hint: Pick items with max value under weight limit [OK]

Common Mistakes:

• Adding weights instead of values
• Choosing items exceeding weight limit
• Misindexing arrays causing wrong dp values

4. Identify the bug in this 0 1 Knapsack DP code snippet:

for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= W; w++) {
        if (weights[i] <= w) {
            dp[i][w] = std::max(dp[i-1][w], dp[i-1][w - weights[i]] + values[i]);
        } else {
            dp[i][w] = dp[i-1][w];
        }
    }
}

medium

A. Indexing weights and values with i instead of i-1

B. Loop ranges should start from 0 instead of 1

C. Using std::max instead of a custom max function

D. Not initializing dp array to zero

Solution

1. Step 1: Check array indexing

   Arrays weights and values are zero-indexed, but code uses i which starts at 1, causing out-of-bound or wrong access.

2. Step 2: Correct indexing

   Use weights[i-1] and values[i-1] to access correct elements.

3. Final Answer:

   Indexing weights and values with i instead of i-1 -> Option A

4. Quick Check:

   Zero-based arrays need i-1 index [OK]

Hint: Use i-1 for zero-based arrays in loops starting at 1 [OK]

Common Mistakes:

• Accessing arrays with wrong index causing runtime errors
• Starting loops at 0 but using i-1 indexing
• Ignoring dp initialization

5. Given items with values {20, 5, 10, 40, 15, 25} and weights {1, 2, 3, 8, 7, 4}, and max weight 10, what is the maximum value achievable using 0 1 Knapsack?

hard

A. 75

B. 65

C. 70

D. 60

Solution

1. Step 1: Analyze items and weight limit

   Items: values = {20,5,10,40,15,25}, weights = {1,2,3,8,7,4}, max weight = 10.

2. Step 2: Find best combination under weight 10

   Choose items with weights 1,3,4 (values 20,10,25) total weight 8, value 55; or items 1,2,6 (weights 1,2,4) value 20+5+25=50; best is items 1,4 (weights 1+8=9) value 20+40=60; or items 4 and 6 (8+4=12 >10) invalid; items 1,5,6 (1+7+4=12 >10) invalid; items 1,3,5 (1+3+7=11 >10) invalid; items 2,3,6 (2+3+4=9) value 5+10+25=40; items 1,2,3,6 (1+2+3+4=10) value 20+5+10+25=60; items 1,2,3,5 (1+2+3+7=13 >10) invalid; items 1,2,3,4 (1+2+3+8=14 >10) invalid; items 1,2,6,5 (1+2+4+7=14 >10) invalid; items 1,3,6 (1+3+4=8) value 20+10+25=55; items 1,2,3,6 total value 60 and weight 10 fits exactly.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   Max value with weight 10 = 60 [OK]

Hint: Try combinations fitting weight limit, sum max values [OK]

Common Mistakes:

• Ignoring weight limit when summing values
• Missing best combination with multiple items
• Assuming greedy choice works always