0/1 Knapsack Problem

📋

0/1 Knapsack Problem

Edge cases:

</>

IDE

def knapsack_recursive(i: int, w: int, weights: list[int], values: list[int]) -> int:public int knapsackRecursive(int i, int w, int[] weights, int[] values)int knapsack_recursive(int i, int w, vector<int>& weights, vector<int>& values)function knapsackRecursive(i, w, weights, values)

def knapsack_recursive(i, w, weights, values):
    # Write your solution here
    pass

class Solution {
    public int knapsackRecursive(int i, int w, int[] weights, int[] values) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int knapsack_recursive(int i, int w, vector<int>& weights, vector<int>& values) {
    // Write your solution here
    return 0;
}

function knapsackRecursive(i, w, weights, values) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Always returning 0 due to missing base case or incorrect initialization.✅ Add base case: if i == 0 or w == 0, return 0.

Wrong: Sum of all values regardless of weightIgnoring weight constraints and including all items.✅ Check if weights[i-1] <= w before including item in dp recurrence.

Wrong: Value greater than correct max (e.g., 120 in t3_02)Using unbounded knapsack logic allowing multiple picks of same item.✅ Ensure DP state includes item index and only considers each item once.

Wrong: Value less than max due to greedy approach (e.g., 80 instead of 90 in t3_01)Greedy selection by value or ratio instead of DP.✅ Implement full DP considering all subsets, not greedy picks.

Wrong: Timeout or no outputExponential brute force solution without memoization or DP.✅ Use bottom-up or top-down DP with memoization to achieve O(n*W) time.

✓

Test Cases

Focus on handling base cases and boundary conditions correctly.

Think about common algorithmic pitfalls like greedy traps and item reuse.

Prepare to optimize your solution for large inputs and time constraints.

t1_01basic

Input{"n":3,"W":50,"weights":[10,20,30],"values":[60,100,120]}

Expected220

⏱ Performance - must finish in 2000ms

Choose items with weights 20 and 30 for total value 100 + 120 = 220 without exceeding capacity 50.

💡 Consider all subsets of items and their total weights and values.

💡 Use dynamic programming to decide whether to include or exclude each item based on capacity.

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

Why it failed: Incorrect output means the recurrence relation is wrong or boundary conditions are mishandled. Fix by ensuring dp includes max of excluding or including item only if weight fits.

✓ Correctly computes max value by considering all items and capacity constraints.

t1_02basic

Input{"n":4,"W":10,"weights":[1,3,4,5],"values":[1,4,5,7]}

Expected12

⏱ Performance - must finish in 2000ms

Choose items with weights 4 and 5 for total value 5 + 7 = 12 without exceeding capacity 10.

💡 Try all combinations to find max value without exceeding capacity.

💡 Check dp table updates for each item and capacity.

💡 Include item if weight allows and value improves total.

Why it failed: If output less than 12, likely ignoring some combinations or not updating dp correctly. Fix by checking both include and exclude cases for each item.

✓ Correctly finds max value 12 by including items 3 and 4.

t2_01edge

Input{"n":0,"W":50,"weights":[],"values":[]}

Expected0

⏱ Performance - must finish in 2000ms

No items to choose from, so max value is 0.

💡 What if there are no items?

💡 Check base case when n=0 returns 0.

💡 Return 0 immediately if no items.

Why it failed: If output not zero, base case for empty input is missing. Fix by returning 0 when n=0.

✓ Correctly handles empty input by returning 0.

t2_02edge

Input{"n":1,"W":10,"weights":[10],"values":[100]}

Expected100

⏱ Performance - must finish in 2000ms

Single item fits exactly into knapsack, so max value is 100.

💡 Check single item cases carefully.

💡 Include item if weight <= capacity.

💡 Return value of item if it fits, else 0.

Why it failed: If output 0, likely ignoring single item inclusion. Fix by checking if single item's weight <= W and returning its value.

✓ Correctly includes single item when it fits.

t2_03edge

Input{"n":3,"W":5,"weights":[6,7,8],"values":[10,20,30]}

Expected0

⏱ Performance - must finish in 2000ms

All items heavier than capacity, so no items can be included, max value 0.

💡 What if all items are heavier than capacity?

💡 Check that no items are included if weight > W.

💡 Return 0 if no items fit.

Why it failed: If output > 0, code incorrectly includes items exceeding capacity. Fix by ensuring items with weight > W are excluded.

✓ Correctly returns 0 when no items fit.

t2_04edge

Input{"n":3,"W":100,"weights":[10,20,30],"values":[60,100,120]}

Expected280

⏱ Performance - must finish in 2000ms

All items fit into knapsack capacity, so max value is sum of all values 60+100+120=280.

💡 Check if total weight of all items is less than or equal to capacity.

💡 If yes, sum all values for max value.

💡 DP should allow including all items if capacity permits.

Why it failed: If output less than 280, code may incorrectly exclude items when all fit. Fix by allowing all items if total weight <= W.

✓ Correctly sums all values when all items fit.

t3_01corner

Input{"n":4,"W":8,"weights":[3,4,5,6],"values":[30,50,60,90]}

Expected90

⏱ Performance - must finish in 2000ms

Greedy approach picking highest value first fails; best is item with weight 6 and value 90.

💡 Greedy by value or value/weight ratio can fail here.

💡 Try all subsets or use DP to find max value.

💡 DP considers all combinations, not just greedy picks.

Why it failed: If output is 80 (e.g., picking items 2 and 1 greedily), greedy approach is wrong. Fix by implementing full DP to consider all subsets.

✓ Correctly avoids greedy trap and finds max value 90.

t3_02corner

Input{"n":3,"W":10,"weights":[2,3,5],"values":[20,30,50]}

Expected100

⏱ Performance - must finish in 2000ms

0/1 knapsack: each item can be chosen once; total max value is 100 by choosing items 2 and 3 (30+50) plus item 1 (20).

💡 Check that items are included at most once.

💡 Avoid unbounded knapsack logic that allows multiple picks.

💡 DP state must consider item index to prevent reuse.

Why it failed: If output > 100, likely unbounded knapsack logic used allowing multiple picks of same item. Fix by ensuring each item is considered once.

✓ Correctly enforces 0/1 constraint and returns 100.

t3_03corner

Input{"n":5,"W":15,"weights":[1,2,3,4,5],"values":[10,20,30,40,50]}

Expected150

⏱ Performance - must finish in 2000ms

All items fit exactly into capacity 15, total value sum is 150.

💡 Check boundary condition when total weight equals capacity.

💡 Ensure DP includes all items if total weight <= W.

💡 Sum all values if all items fit.

Why it failed: If output less than 150, code may incorrectly exclude items when total weight equals capacity. Fix by allowing items to fill capacity exactly.

✓ Correctly handles exact boundary and sums all values.

t4_01performance

Input{"n":100,"W":1000,"weights":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50],"values":[50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, W=1000, O(n*W) DP must complete within 2 seconds.

💡 Brute force exponential solutions will time out here.

💡 Use bottom-up DP with O(n*W) complexity.

💡 Optimize space by using 1D DP array if possible.

Why it failed: TLE indicates exponential or inefficient approach. Fix by implementing O(n*W) DP solution.

✓ Efficient DP solution runs within time limits.

Practice

1. You are given a set of positive integers and need to partition it into two subsets such that the absolute difference of their sums is minimized. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that sorts and assigns elements alternately to subsets

B. Dynamic programming using a subset-sum style approach to find achievable sums

C. Divide and conquer by recursively splitting the array into halves

D. Sorting and then pairing elements from opposite ends to balance sums

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing the difference between sums of two subsets, which is a classic partition problem variant.

2. Step 2: Identify algorithmic pattern

   Greedy or divide-and-conquer approaches do not guarantee minimal difference. Dynamic programming, specifically subset-sum style DP, can find all achievable sums up to total_sum, enabling minimal difference calculation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP subset-sum approach guarantees optimal partition [OK]

Hint: Minimal difference requires subset-sum DP, not greedy [OK]

Common Mistakes:

• Assuming greedy or sorting suffices for minimal difference

2. You are given an array of positive integers and a number k. The task is to determine if the array can be partitioned into k subsets such that the sum of elements in each subset is equal. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that repeatedly picks the largest element and tries to fit it into subsets

B. Dynamic programming with bitmask tabulation that tracks subset sums for all combinations

C. Simple backtracking without memoization that tries all possible assignments

D. Sorting the array and using a two-pointer technique to pair elements

Solution

1. Step 1: Understand problem constraints

   The problem requires partitioning into equal sum subsets, which is a classic NP-complete problem requiring exploration of subsets.

2. Step 2: Identify algorithmic pattern

   Dynamic programming with bitmask tabulation efficiently explores all subsets and tracks partial sums modulo target, guaranteeing optimality.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask DP covers all subsets systematically [OK]

Hint: Bitmask DP tracks all subset sums efficiently [OK]

Common Mistakes:

• Assuming greedy always works for equal sum partition
• Using backtracking without memoization leads to timeouts

3. The following code attempts to solve the Equal Partition problem using a 1D DP array. Which line contains a subtle bug that can cause incorrect results on some inputs?

def canPartition(nums):
    total = sum(nums)
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for w in range(num, target + 1):
            dp[w] = dp[w] or dp[w - num]

    return dp[target]

medium

A. Line 2: Missing check if total is even before proceeding

B. Line 4: Initializing dp array with false instead of true

C. Line 6: Iterating forwards in dp array instead of backwards

D. Line 8: Returning dp[target] without verifying dp array correctness

Solution

1. Step 1: Identify missing even check

   Line 2 does not check if total is even, but this causes no incorrect dp updates, only wasted computation.

2. Step 2: Analyze dp iteration direction

   Line 6 iterates forwards, which causes reuse of updated dp values in the same iteration, leading to counting elements multiple times and incorrect results.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backward iteration is required to avoid reusing updated dp values in the same iteration [OK]

Hint: DP must iterate backwards to avoid reuse in 1D array [OK]

Common Mistakes:

• Iterating forwards in dp updates
• Skipping even sum check

4. What is the time complexity of the space-optimized bottom-up subset sum algorithm given an input list of size n and target sum S?

medium

A. O(2^n)

B. O(n + S)

C. O(n * S)

D. O(n * log S)

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm has an outer loop over n elements and an inner loop over sums from S down to each num.

2. Step 2: Calculate total operations

   Each element causes up to S iterations, so total time is O(n * S). Recursive brute force is exponential, and linear or log factors are incorrect.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops over n and S -> O(n * S) [OK]

Hint: Nested loops over n and S -> multiply complexities [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming linear or exponential time incorrectly

5. Suppose the problem is modified so that you want to find the minimum number of perfect squares summing to n, but now each perfect square can only be used at most once. Which of the following changes correctly adapts the algorithm?

hard

A. Keep the same bottom-up DP but iterate squares in increasing order and update dp[i] from dp[i - square] without reuse

B. Use a top-down memoized recursion with a visited set to avoid reusing squares

C. Use a 2D DP array where dp[i][j] represents minimum squares using first j squares to sum to i

D. Change the inner loop to iterate over squares in decreasing order and update dp[i] accordingly

Solution

1. Step 1: Understand the constraint change

   Limiting each perfect square to be used at most once converts the problem from unbounded to 0/1 knapsack variant, requiring tracking which squares are used.

2. Step 2: Identify correct DP adaptation

   A 2D DP array dp[i][j] that tracks minimum squares to sum to i using first j squares correctly models the usage constraint. Other options either do not prevent reuse or do not track usage properly.

3. Step 3: Confirm why other options fail

   Keep the same bottom-up DP but iterate squares in increasing order and update dp[i] from dp[i - square] without reuse still allows reuse implicitly. Use a top-down memoized recursion with a visited set to avoid reusing squares is inefficient and complex. Change the inner loop to iterate over squares in decreasing order and update dp[i] accordingly's order change alone doesn't enforce usage limits.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   0/1 knapsack requires 2D DP to track usage [OK]

Hint: At-most-once usage -> 0/1 knapsack -> 2D DP needed [OK]

Common Mistakes:

• Trying to reuse unbounded DP
• Ignoring usage constraints in DP state