0 1 Knapsack Problem in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the '0 1' in the 0 1 Knapsack Problem mean?

It means each item can either be taken completely (1) or not taken at all (0). You cannot take fractional parts of an item.

beginner

What is the main goal of the 0 1 Knapsack Problem?

To maximize the total value of items placed in the knapsack without exceeding its weight capacity.

intermediate

Which technique is commonly used to solve the 0 1 Knapsack Problem efficiently?

Dynamic Programming is commonly used to solve it efficiently by building a table of solutions for smaller subproblems.

intermediate

In the dynamic programming solution, what does the table entry dp[i][w] represent?

It represents the maximum value achievable using the first i items with a knapsack capacity of w.

intermediate

Why can't greedy algorithms solve the 0 1 Knapsack Problem optimally?

Because choosing items based only on value or weight ratio can miss combinations that yield higher total value within capacity constraints.

In the 0 1 Knapsack Problem, what is NOT allowed?

A Taking fractional parts of an item

B Taking an item completely

C Skipping an item

D Maximizing total value

The 0 1 Knapsack Problem only allows taking whole items or skipping them, no fractions.

What does dp[i][w] store in the dynamic programming solution?

A Maximum value using first i items with capacity w

B Weight of the ith item

C Total number of items

D Minimum weight to achieve value w

dp[i][w] stores the best value achievable with first i items and capacity w.

Which approach is best to solve the 0 1 Knapsack Problem optimally?

A Brute Force only

B Greedy Algorithm

C Dynamic Programming

D Divide and Conquer

Dynamic Programming efficiently solves the problem by reusing solutions to subproblems.

What is the time complexity of the classic dynamic programming solution for 0 1 Knapsack?

A O(n^2)

B O(n * W)

C O(W^2)

D O(n + W)

The DP solution runs in O(n * W), where n is number of items and W is capacity.

If you have items with weights [1, 3, 4] and values [15, 20, 30], and capacity 4, what is the maximum value you can carry?

A 20

B 30

C 15

D 35

Taking items with weights 1 and 3 gives total value 15 + 20 = 35 within capacity 4.

Explain how dynamic programming solves the 0 1 Knapsack Problem step-by-step.

Think about how smaller problems build up to the full solution.

Describe why greedy methods fail for the 0 1 Knapsack Problem and give an example.

Consider items with high value but heavy weight.

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