0 1 Knapsack Problem in DSA Python

Mental Model

We want to pick items with values and weights to maximize value without exceeding 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 usefulness (value) and sizes (weight). You want to pack the most useful combination without overloading.

Items: [value, weight]
[60, 10]  [100, 20]  [120, 30]
Knapsack capacity: 50

Backpack capacity -> 50
Items to choose -> 3

Initial DP table (rows: items, cols: weight capacity):
0 -> 1 -> 2 -> ... -> 50
0 -> 0 -> 0 -> ... -> 0
↑
Item 0 (no items chosen yet)

Dry Run Walkthrough

Input: items: [(60,10), (100,20), (120,30)], capacity: 50

Goal: Find max value by choosing items without exceeding capacity 50

Step 1: Consider first item (60 value, 10 weight), fill DP for capacities 0 to 50

DP row 1: For weights <10 -> 0, weights ≥10 -> 60

Why: We can only take first item once if it fits, so value is 60 for capacities 10 and above

Step 2: Consider second item (100 value, 20 weight), update DP row 2

For capacity 20: max(60 from previous, 100 from second item) = 100
For capacity 30: max(60, 100 + 60 from capacity 10) = 160
For capacity 50: max(60, 100 + 60) = 160

Why: We check if adding second item plus best from remaining capacity is better than previous best

Step 3: Consider third item (120 value, 30 weight), update DP row 3

For capacity 30: max(160 from previous, 120) = 160
For capacity 50: max(160, 120 + 100 from capacity 20) = 220

Why: We try adding third item plus best from leftover capacity to maximize value

Result:

DP last row at capacity 50 = 220
Max value = 220

Annotated Code

DSA Python

class Knapsack:
    def __init__(self, values, weights, capacity):
        self.values = values
        self.weights = weights
        self.capacity = capacity
        self.n = len(values)

    def solve(self):
        dp = [[0] * (self.capacity + 1) for _ in range(self.n + 1)]

        for i in range(1, self.n + 1):
            for w in range(self.capacity + 1):
                if self.weights[i - 1] <= w:
                    dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - self.weights[i - 1]] + self.values[i - 1])
                else:
                    dp[i][w] = dp[i - 1][w]
        return dp[self.n][self.capacity]


if __name__ == '__main__':
    values = [60, 100, 120]
    weights = [10, 20, 30]
    capacity = 50
    knapsack = Knapsack(values, weights, capacity)
    print(knapsack.solve())

for i in range(1, self.n + 1):

iterate over each item to consider including it or not

for w in range(self.capacity + 1):

iterate over all possible capacities from 0 to max capacity

if self.weights[i - 1] <= w:

check if current item fits in current capacity

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

choose max between not taking or taking current item plus best value for leftover capacity

else: dp[i][w] = dp[i - 1][w]

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

Output

220

Complexity Analysis

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

Space: O(n * capacity) because we store results for each item and capacity combination

vs Alternative: Naive approach tries all subsets (2^n), which is much slower than DP's polynomial time

Edge Cases

Empty items list

Returns 0 as no items to choose

DSA Python

for i in range(1, self.n + 1):

Capacity zero

Returns 0 as no capacity to hold items

DSA Python

for w in range(self.capacity + 1):

Items heavier than capacity

Items skipped, result is 0 or max of lighter items

DSA Python

if self.weights[i - 1] <= w:

When to Use This Pattern

When you need to pick items with weights and values to maximize value without splitting items, use 0 1 Knapsack DP to efficiently find the best combination.

Common Mistakes

Mistake: Using capacity index incorrectly causing index errors
Fix: Always check weights[i-1] against w and use dp[i-1][w - weights[i-1]] carefully

Mistake: Not initializing dp table with zeros causing garbage values
Fix: Initialize dp with zeros for base cases

Summary

Find max value of items fitting in capacity without splitting items.

Use when you must choose whole items to maximize value under weight limit.

The key is building a table of best values for each item count and capacity step.

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