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

Recall & Review

beginner

What is the 0 1 Knapsack Problem?

It is a problem where you have a set of items, each with a weight and value. You want to pick items to maximize value without exceeding a weight limit. You can either take an item or leave it (no partial items).

beginner

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

It means each item can be chosen only once (1) or not chosen at all (0). You cannot take fractions or multiple copies of the same item.

intermediate

What is the main idea behind solving the 0 1 Knapsack Problem using dynamic programming?

We build a table where each cell shows the best value possible with a certain number of items and weight limit. We decide for each item whether to include it or not based on maximizing value.

intermediate

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

The time complexity is O(n * W), where n is the number of items and W is the maximum weight capacity of the knapsack.

beginner

In the 0 1 Knapsack Problem, if an item weighs more than the current weight limit, what do we do?

We skip that item because it cannot fit in the knapsack at that weight limit. So, the best value remains the same as without that item.

In the 0 1 Knapsack Problem, what does each entry dp[i][w] represent?

A Minimum weight to achieve value w using i items

B Maximum value using first i items with weight limit w

C Number of items chosen with weight w

D Total weight of first i items

dp[i][w] stores the best value achievable using the first i items without exceeding weight w.

If an item has weight 5 and value 10, and the current weight limit is 3, what happens in the 0 1 Knapsack DP?

A Item is included

B Item value is halved

C Item is partially included

D Item is excluded

Since the item weight exceeds the current limit, it cannot be included.

What is the base case for the 0 1 Knapsack DP table?

A Both A and B

B dp[i][0] = 0 for all i

C dp[0][w] = 0 for all w

D dp[i][w] = value of item i

When no items or zero weight capacity, maximum value is zero.

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

A Divide and conquer

B Greedy algorithm

C Dynamic programming

D Brute force only

Dynamic programming efficiently solves it by storing intermediate results.

Can the 0 1 Knapsack Problem be solved by taking fractional parts of items?

A No, only whole items allowed

B Only for items with value less than weight

C Only if items are divisible

D Yes, always

0 1 Knapsack means items are either taken whole or not at all.

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

Think about choices for each item and how to store best values.

Describe the difference between 0 1 Knapsack and Fractional Knapsack problems.

Focus on item selection rules and solution methods.

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 value of items without exceeding the weight limit

B. The total weight of items regardless of value

C. The number of items selected

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: Clarify constraints

   Each item can be chosen only once (0 or 1 times), so the goal is to maximize value under weight limit.

3. Final Answer:

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

4. Quick Check:

   Maximize value under weight limit = The total value of items without exceeding the weight limit [OK]

Hint: Focus on maximizing value, not weight or count [OK]

Common Mistakes:

• Confusing weight maximization with value maximization
• Thinking the problem counts items instead of values
• Ignoring the weight limit constraint

2. Which of the following is the correct Python syntax to initialize a 2D list dp of size (n+1) x (W+1) filled with zeros for the 0 1 Knapsack DP table?

easy

A. dp = [[0 for _ in range(W+1)] for _ in range(n+1)]

B. dp = [[0] * n for _ in range(W)]

C. dp = [0] * (n+1) * (W+1)

D. dp = [[0] * (W+1)] * (n+1)

Solution

1. Step 1: Understand 2D list initialization

   Using list comprehension with nested loops creates independent inner lists, avoiding shared references.

2. Step 2: Analyze each option

   dp = [[0 for _ in range(W+1)] for _ in range(n+1)] correctly uses nested list comprehension to create a (n+1) x (W+1) zero matrix.

3. Final Answer:

   dp = [[0 for _ in range(W+1)] for _ in range(n+1)] -> Option A

4. Quick Check:

   Nested list comprehension for 2D zero matrix = dp = [[0 for _ in range(W+1)] for _ in range(n+1)] [OK]

Hint: Use nested list comprehension for 2D lists [OK]

Common Mistakes:

• Using multiplication for inner lists causing shared references
• Creating 1D list instead of 2D
• Swapping dimensions incorrectly

3. What is the output of the following Python code snippet implementing 0 1 Knapsack DP for items with weights [1, 2, 3] and values [10, 20, 30] and capacity 5?

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            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][W]

print(knapsack([1,2,3], [10,20,30], 5))

medium

A. 60

B. 40

C. 50

D. 30

Solution

1. Step 1: Trace DP table filling

   Items: (1,10), (2,20), (3,30), Capacity=5. Check combinations:
   - Take items 2 and 3: weight=5, value=50
   - Take items 1 and 3: weight=4, value=40
   - Take all items 1,2,3: weight=6 (exceeds capacity)
   - Take items 1 and 2: weight=3, value=30

2. Step 2: Find max value within capacity

   Best is items 2 and 3 with total value 50, but check if better:
   Actually, items 1,2,3 total weight 6 > 5, so not allowed.
   Items 1,2,3 can't all be taken.
   Check items 1,2,3 subsets:
   Items 2,3: 5 weight, 50 value
   Items 1,3: 4 weight, 40 value
   Items 1,2: 3 weight, 30 value
   So max value is 50.

3. Final Answer:

   50 -> Option C

4. Quick Check:

   Max value under weight 5 = 50 [OK]

Hint: Check all item subsets under capacity for max value [OK]

Common Mistakes:

• Assuming all items fit without checking weight
• Mixing up indices in DP table
• Forgetting to subtract weight when adding value

4. Find the error in this 0 1 Knapsack DP code snippet and select the fix:

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            if weights[i] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i]] + values[i])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

medium

A. Change range(1, W+1) to range(W)

B. Change dp[i-1][w] to dp[i][w]

C. Initialize dp with ones instead of zeros

D. Change weights[i] to weights[i-1] and values[i] to values[i-1]

Solution

1. Step 1: Identify index error in array access

   Python lists are zero-indexed, but loop uses i from 1 to n, so weights[i] and values[i] cause IndexError or wrong access.

2. Step 2: Correct indexing for weights and values

   Use weights[i-1] and values[i-1] to access correct item corresponding to dp row i.

3. Final Answer:

   Change weights[i] to weights[i-1] and values[i] to values[i-1] -> Option D

4. Quick Check:

   Fix indexing to avoid off-by-one errors = Change weights[i] to weights[i-1] and values[i] to values[i-1] [OK]

Hint: Use i-1 to index weights and values inside loops [OK]

Common Mistakes:

• Using i instead of i-1 for zero-based lists
• Changing dp indices incorrectly
• Altering loop ranges unnecessarily

5. Given items with weights [2, 3, 4, 5] and values [3, 4, 5, 6], and a knapsack capacity of 5, which items should be selected to maximize value? Also, what is the maximum value achievable?

hard

A. Select item with weight 5 only; max value 6

B. Select items with weights 2 and 3; max value 7

C. Select items with weights 3 and 4; max value 9

D. Select items with weights 2 and 4; max value 8

Solution

1. Step 1: List possible item combinations under capacity 5

   Check combinations:
   - Item 1 (2,3) + Item 2 (3,4): total weight 5, value 7
   - Item 3 (4,5) alone: weight 4, value 5
   - Item 4 (5,6) alone: weight 5, value 6
   - Item 2 (3,4) + Item 3 (4,5): weight 7 (exceeds capacity)
   - Item 1 (2,3) + Item 3 (4,5): weight 6 (exceeds capacity)

2. Step 2: Choose combination with max value

   Items 1 and 2 together fit exactly and give value 7, which is higher than any single item value under capacity.

3. Final Answer:

   Select items with weights 2 and 3; max value 7 -> Option B

4. Quick Check:

   Max value with capacity 5 = 7 by items 2 and 3 weights [OK]

Hint: Try all item pairs fitting capacity, pick max value [OK]

Common Mistakes:

• Choosing heavier single item over lighter combo
• Ignoring exact capacity limit
• Assuming max value is from single item