0/1 Knapsack and Unbounded Knapsack

0/1 Knapsack Problems

In 0/1 Knapsack, each item can be used at most once.

Classic 0/1 Problems

1. Partition Equal Subset Sum (LC-416) [Medium]

   • Given array nums, determine if it can be partitioned into two equal sum subsets
   • Classic 0/1 where target sum is total/2

   canPartition([1,5,11,5]) // true -> [1,5,5] and [11]

2. Target Sum (LC-494) [Medium]

   • Assign + or - to each number to achieve target sum
   • 0/1 where each number must be used exactly once

   findTargetSum([1,1,1,1,1], 3) // 5 ways

3. Last Stone Weight II (LC-1049) [Medium]

   • Smash stones together to minimize final weight
   • Transforms into finding closest possible partition

   lastStoneWeightII([2,7,4,1,8,1]) // 1

4. Ones and Zeroes (LC-474) [Medium]

   • Find largest subset with limited 0s and 1s
   • 0/1 with two constraints (m zeros, n ones)

   findMaxForm(["10","0001","111001","1","0"], m=5, n=3)

Subset Problems (0/1 Variants)

5. Subsets II (LC-90) [Medium]

   • Generate all possible subsets with duplicates
   • Each number can be used 0 or 1 times

   subsetsWithDup([1,2,2]) // [[],[1],[2],[1,2],[2,2],[1,2,2]]

6. Partition to K Equal Sum Subsets (LC-698) [Medium]

   • Partition array into k subsets with equal sums
   • Each number must be used exactly once

   canPartitionKSubsets([4,3,2,3,5,2,1], k=4) // true

Unbounded Knapsack Problems

In Unbounded Knapsack, items can be used multiple times.

Classic Unbounded Problems

1. Coin Change (LC-322) [Medium]

   • Minimum coins needed to make amount
   • Each coin can be used unlimited times

   coinChange([1,2,5], amount=11) // 3 coins

2. Coin Change II (LC-518) [Medium]

   • Number of ways to make amount using coins
   • Unlimited use of each coin

   change(amount=5, coins=[1,2,5]) // 4 ways

3. Perfect Squares (LC-279) [Medium]

   • Minimum number of perfect squares that sum to n
   • Can use same square multiple times

   numSquares(12) // 3 (4+4+4)

4. Integer Break (LC-343) [Medium]

   • Break integer into sum of numbers to maximize product
   • Can reuse numbers

   integerBreak(10) // 36 (3+3+4)

Combination Problems (Unbounded Variants)

5. Combination Sum (LC-39) [Medium]

   • Find all combinations that sum to target
   • Can reuse numbers

   combinationSum([2,3,6,7], target=7) // [[2,2,3],[7]]

6. Combination Sum IV (LC-377) [Medium]

   • Number of possible combinations that sum to target
   • Order matters (true combinations)

   combinationSum4([1,2,3], target=4) // 7 combinations

Implementation Tips

0/1 Knapsack Template

function knapsack01(values, weights, capacity) {
    const n = values.length;
    const dp = Array(capacity + 1).fill(0);
    
    for (let i = 0; i < n; i++) {
        for (let w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    
    return dp[capacity];
}

Unbounded Knapsack Template

function unboundedKnapsack(values, weights, capacity) {
    const n = values.length;
    const dp = Array(capacity + 1).fill(0);
    
    for (let w = 1; w <= capacity; w++) {
        for (let i = 0; i < n; i++) {
            if (weights[i] <= w) {
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
    }
    
    return dp[capacity];
}

Key Differences

1. Iteration Order

   • 0/1: Must iterate capacity backwards to avoid reusing items
   • Unbounded: Can iterate forwards since reuse is allowed

2. State Transition

   • 0/1: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
   • Unbounded: dp[w] = max(dp[w], dp[w-weight[i]] + value[i])

3. Space Optimization

   • 0/1: Can optimize to 1D array but must iterate backwards
   • Unbounded: Naturally uses 1D array with forward iteration

Common Patterns to Watch For

1. Sum Division Problems

   • If problem involves dividing sum into parts
   • Usually 0/1 Knapsack variant

2. Minimizing Differences

   • Finding minimum difference between partitions
   • Transform into 0/1 Knapsack

3. Combination Problems

   • If order doesn't matter: Usually 0/1
   • If order matters or reuse allowed: Usually Unbounded

4. Multiple Constraints

   • May need multiple dp arrays
   • Example: Ones and Zeroes problem

Fractional Knapsack Problems

In Fractional Knapsack, items can be broken into smaller units (unlike 0/1 and unbounded).

Key Characteristics

• Items can be divided into fractions
• Usually requires sorting by value/weight ratio
• Greedy approach works (unlike 0/1 and unbounded)
• Optimal solution always includes the best ratio items first

Implementation Template

function fractionalKnapsack(values, weights, capacity) {
    const n = values.length;
    const items = [];
    
    // Create items with value/weight ratio
    for (let i = 0; i < n; i++) {
        items.push({
            value: values[i],
            weight: weights[i],
            ratio: values[i] / weights[i]
        });
    }
    
    // Sort by value/weight ratio in descending order
    items.sort((a, b) => b.ratio - a.ratio);
    
    let totalValue = 0;
    let currentWeight = 0;
    
    for (let item of items) {
        if (currentWeight + item.weight <= capacity) {
            // Take whole item
            currentWeight += item.weight;
            totalValue += item.value;
        } else {
            // Take fraction of the item
            const remainingCapacity = capacity - currentWeight;
            totalValue += item.value * (remainingCapacity / item.weight);
            break;
        }
    }
    
    return totalValue;
}

Related Problems

1. Container With Most Water (LC-11) [Medium]

   • While not strictly fractional knapsack, uses similar principles
   • Area represents "value" that can be partially used

   maxArea([1,8,6,2,5,4,8,3,7]) // 49

2. Minimum Number of Refueling Stops (LC-871) [Hard]

   • Car with initial fuel capacity
   • Can take partial fuel from stations

   minRefuelStops(target, startFuel, stations)

3. Maximum Performance of a Team (LC-1383) [Hard]

   • Select team members with speed/efficiency ratios
   • Partial contribution to team performance

   maxPerformance(n, speed, efficiency, k)

Comparison with Other Knapsack Types

Time Complexity

1. 0/1 Knapsack: O(nW) - Dynamic Programming
2. Unbounded Knapsack: O(nW) - Dynamic Programming
3. Fractional Knapsack: O(n log n) - Greedy with sorting

Space Complexity

1. 0/1 Knapsack: O(W) or O(nW)
2. Unbounded Knapsack: O(W)
3. Fractional Knapsack: O(n) for storing items

Solution Approach

1. 0/1 Knapsack: Dynamic Programming
2. Unbounded Knapsack: Dynamic Programming
3. Fractional Knapsack: Greedy Algorithm

When to Use Each Type

1. Use 0/1 Knapsack when:

   • Items must be used completely or not at all
   • Each item can be used at most once
   • Example: Filling a backpack with indivisible items

2. Use Unbounded Knapsack when:

   • Items must be used completely
   • Items can be used multiple times
   • Example: Making change with coins

3. Use Fractional Knapsack when:

   • Items can be divided into smaller units
   • Value is proportional to the amount used
   • Example: Filling a container with liquids

Implementation Differences

// Different approaches for each type
function compareKnapsackTypes(values, weights, capacity) {
    // 0/1 Knapsack - Dynamic Programming
    function knapsack01() {
        const dp = Array(capacity + 1).fill(0);
        for (let i = 0; i < values.length; i++) {
            for (let w = capacity; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        return dp[capacity];
    }

    // Unbounded Knapsack - Dynamic Programming
    function unboundedKnapsack() {
        const dp = Array(capacity + 1).fill(0);
        for (let w = 1; w <= capacity; w++) {
            for (let i = 0; i < values.length; i++) {
                if (weights[i] <= w) {
                    dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
                }
            }
        }
        return dp[capacity];
    }

    // Fractional Knapsack - Greedy
    function fractionalKnapsack() {
        const items = values.map((v, i) => ({
            value: v,
            weight: weights[i],
            ratio: v / weights[i]
        }));
        items.sort((a, b) => b.ratio - a.ratio);
        
        let totalValue = 0;
        let currentWeight = 0;
        
        for (let item of items) {
            if (currentWeight + item.weight <= capacity) {
                currentWeight += item.weight;
                totalValue += item.value;
            } else {
                const remaining = capacity - currentWeight;
                totalValue += item.value * (remaining / item.weight);
                break;
            }
        }
        return totalValue;
    }

    return {
        zeroOne: knapsack01(),
        unbounded: unboundedKnapsack(),
        fractional: fractionalKnapsack()
    };
}

Optimization Tips

1. For Fractional Knapsack:

   • Pre-calculate and store ratios
   • Use quick select instead of sorting for k largest ratios
   • Consider using a heap for large datasets
   • Cache ratio calculations if used multiple times

2. Common Optimizations Across All Types:

   • Early termination when capacity is filled
   • Preprocessing to remove invalid items
   • Space optimization in DP solutions
   • Bit manipulation for small weights