🎒 Knapsack Fundamentals

🎯 What is the Knapsack Problem?

The knapsack problem is a classic optimization problem: given a set of items with weights and values, choose a subset to maximize total value while staying within a weight capacity. It's one of the most studied problems in computer science.

Input: Items (weight, value), capacity W
Output: Max total value
Constraint: Total weight ≤ W
Goal: Maximize total value

📌 NP-Complete (0/1)📌 Greedy works for Fractional📌 DP for 0/1 & Unbounded

The Core Challenge

Key Insight: The knapsack problem forces us to make decisions about which items to include. The 0/1 variant (each item at most once) is NP-Complete, making it a cornerstone of algorithmic study.

Main Variants:

0/1 Knapsack Each item once (DP)
Unbounded Each item unlimited (DP)
Fractional Can take fractions (Greedy)

# Knapsack Problem Statement
# Given:
#   n = number of items
#   weights = [w1, w2, ..., wn]
#   values = [v1, v2, ..., vn]
#   capacity = W

# Maximize: sum of values of chosen items
# Subject to: sum of weights of chosen items ≤ W

# 0/1 Constraint: each item can be taken at most once
# Unbounded: each item can be taken any number of times

📦 0/1 Knapsack (Classic)

🎯 The Classic DP Problem

Each item can be taken at most once. This is the most famous knapsack variant and a cornerstone of dynamic programming.

State: dp[i][w] = max value using first i items with capacity w
Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
Base: dp[0][w] = 0, dp[i][0] = 0
Time: O(n * W) | Space: O(n * W) or O(W) optimized

# 0/1 Knapsack - Full DP Table
def knapsack_01(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]

# Space-Optimized (1D Array)
def knapsack_01_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    
    for i in range(n):
        # Iterate backwards to avoid using the same item multiple times
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[W]

# Example:
# weights = [2, 3, 4, 5]
# values = [3, 4, 5, 6]
# W = 5
# Optimal: take items 1 and 2 (weight 5, value 7)

🔄 Unbounded Knapsack

🎯 Unlimited Items

Each item can be taken an unlimited number of times. Also known as the "complete knapsack" problem.

State: dp[w] = max value achievable with capacity w
Recurrence: dp[w] = max(dp[w], dp[w - weight[i]] + value[i])
Base: dp[0] = 0
Time: O(n * W) | Space: O(W)

# Unbounded Knapsack
def knapsack_unbounded(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    
    # Iterate forward to allow unlimited use
    for w in range(1, W + 1):
        for i in range(n):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[W]

# Alternative: Iterate items first (also works)
def knapsack_unbounded_alt(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    
    for i in range(n):
        for w in range(weights[i], W + 1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[W]

# Example:
# weights = [2, 3, 4]
# values = [3, 4, 5]
# W = 7
# Optimal: take item 0 twice (weight 4, value 6) + item 1 (weight 3, value 4)
# Total weight 7, value 10

📊 Bounded Knapsack

🎯 Limited Item Quantities

Each item has a limited quantity (count[i] copies available). This is a generalization of 0/1 and unbounded knapsack.

State: dp[w] = max value with capacity w
Approach 1: Convert to 0/1 by expanding items
Approach 2: Binary splitting (O(log count) items)
Approach 3: Monotonic queue optimization

# Bounded Knapsack with Binary Splitting
def knapsack_bounded(weights, values, counts, W):
    # Binary split each item into powers of 2
    new_weights = []
    new_values = []
    
    for i in range(len(weights)):
        k = 1
        while counts[i] > 0:
            take = min(k, counts[i])
            new_weights.append(weights[i] * take)
            new_values.append(values[i] * take)
            counts[i] -= take
            k *= 2
    
    # Now solve as 0/1 knapsack
    dp = [0] * (W + 1)
    for i in range(len(new_weights)):
        for w in range(W, new_weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - new_weights[i]] + new_values[i])
    
    return dp[W]

# Example:
# weights = [2, 3]
# values = [3, 4]
# counts = [3, 2]  # 3 copies of item 0, 2 copies of item 1
# W = 10
# Optimal: take 3 of item 0 (weight 6, value 9) + 1 of item 1 (weight 3, value 4)
# Total weight 9, value 13

🧮 Fractional Knapsack (Greedy)

🎯 Greedy Wins!

Items can be divided (take fractions). This is the only knapsack variant where the greedy algorithm is optimal.

Greedy Strategy: Sort by value/weight ratio (density)
Take items: Full items until capacity insufficient, then take fraction
Time: O(n log n) for sorting | Space: O(1) extra

# Fractional Knapsack - Greedy
def knapsack_fractional(weights, values, W):
    n = len(weights)
    # Calculate value/weight ratio
    items = [(values[i] / weights[i], weights[i], values[i]) for i in range(n)]
    items.sort(key=lambda x: x[0], reverse=True)
    
    total_value = 0.0
    remaining_capacity = W
    
    for ratio, weight, value in items:
        if weight <= remaining_capacity:
            total_value += value
            remaining_capacity -= weight
        else:
            total_value += ratio * remaining_capacity
            break
    
    return total_value

# Example:
# weights = [10, 20, 30]
# values = [60, 100, 120]
# W = 50
# Ratios: 6, 5, 4
# Take all of item 0 (weight 10, value 60)
# Take all of item 1 (weight 20, value 100)
# Take 20/30 of item 2 (weight 20, value 80)
# Total value = 240

📦 Multiple Knapsack

🎯 Multiple Knapsacks

We have multiple knapsacks (capacities) and items must be assigned to knapsacks. Each item can be placed in exactly one knapsack.

State: dp[i][c1][c2]... - multi-dimensional DP
Approach: DP over items and capacities
Alternative: LP / ILP formulation

# Multiple Knapsack (2 knapsacks)
def knapsack_multiple(weights, values, cap1, cap2):
    n = len(weights)
    # dp[i][j] = max value using first i items with capacities j and (cap2)
    dp = [[0] * (cap2 + 1) for _ in range(cap1 + 1)]
    
    for i in range(n):
        # Iterate backwards for 0/1 behavior (each item once)
        for c1 in range(cap1, -1, -1):
            for c2 in range(cap2, -1, -1):
                # Skip item
                best = dp[c1][c2]
                # Put in first knapsack
                if c1 >= weights[i]:
                    best = max(best, dp[c1 - weights[i]][c2] + values[i])
                # Put in second knapsack
                if c2 >= weights[i]:
                    best = max(best, dp[c1][c2 - weights[i]] + values[i])
                dp[c1][c2] = best
    
    return dp[cap1][cap2]

🎯 Subset Sum Problem

🎯 Can we make exactly the target sum?

Given a set of numbers, is there a subset that sums to exactly a target? This is a special case of knapsack where values = weights.

State: dp[w] = true if sum w is achievable
Recurrence: dp[w] = dp[w] OR dp[w - weights[i]]
Base: dp[0] = true
Time: O(n * W) | Space: O(W)

# Subset Sum (0/1)
def subset_sum(weights, target):
    n = len(weights)
    dp = [False] * (target + 1)
    dp[0] = True
    
    for i in range(n):
        for w in range(target, weights[i] - 1, -1):
            dp[w] = dp[w] or dp[w - weights[i]]
    
    return dp[target]

# Example:
# weights = [2, 3, 7, 8, 10]
# target = 11
# Can we make 11? Yes: 3 + 8 = 11

# Unbounded Subset Sum (Coin Change)
def subset_sum_unbounded(weights, target):
    dp = [False] * (target + 1)
    dp[0] = True
    
    for w in range(1, target + 1):
        for weight in weights:
            if weight <= w:
                dp[w] = dp[w] or dp[w - weight]
    
    return dp[target]

⚖️ Partition Equal Subset Sum

🎯 Split into Two Equal Sum Subsets

Can the array be partitioned into two subsets with equal sum? This reduces to subset sum with target = total_sum / 2.

Check: If total_sum is odd → false
Target: total_sum // 2
Solve: Subset sum with target

# Partition Equal Subset Sum
def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for w in range(target, num - 1, -1):
            dp[w] = dp[w] or dp[w - num]
    
    return dp[target]

# Example:
# nums = [1, 5, 11, 5]
# total = 22, target = 11
# Partition: [1, 5, 5] and [11] → True

# nums = [1, 2, 3, 5]
# total = 11, target = 5.5 → False (odd sum)

⚡ DP Optimization for Knapsack

🎯 Advanced Optimizations

Space Optimization: 2D → 1D rolling array
Binary Splitting: O(n * W * log count) for bounded
Monotonic Queue: O(n * W) for bounded (best)
Meet-in-the-Middle: O(2^(n/2)) for small n
Branch and Bound: For exact solutions with pruning
Approximation: FPTAS for approximate solutions

🌀 Knapsack Variations

Knapsack with Item Dependencies: Some items require others
Multi-Dimensional Knapsack: Multiple constraints (weight, volume, etc.)
Knapsack with Profits and Weights: Maximize profit with weight constraint
Minimization Knapsack: Minimize cost to achieve certain value
Group Knapsack: Choose exactly one item from each group
Knapsack with Discounts: Discounts for buying multiple items
Knapsack with Setup Costs: Fixed cost for including items

🔍 Reconstructing the Solution

🎯 Getting the Actual Items

Sometimes we need to know which items are selected, not just the maximum value. This requires backtracking through the DP table.

# 0/1 Knapsack with Reconstruction
def knapsack_reconstruct(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    # Fill DP table
    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]
    
    # Backtrack to find selected items
    selected = []
    w = W
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            selected.append(i-1)
            w -= weights[i-1]
    
    return dp[n][W], selected

# Example:
# weights = [2, 3, 4, 5]
# values = [3, 4, 5, 6]
# W = 5
# Returns: (7, [0, 1]) meaning items 0 and 1 (weight 5, value 7)

⏱️ Time & Space Complexities

Variant	Time Complexity	Space Complexity	Algorithm
0/1 Knapsack	O(n × W)	O(n × W) or O(W)	DP
Unbounded	O(n × W)	O(W)	DP
Bounded (Binary Split)	O(n × W × log count)	O(W)	DP + Binary
Fractional	O(n log n)	O(1)	Greedy
Subset Sum	O(n × W)	O(W)	DP
Partition	O(n × sum/2)	O(sum/2)	DP

🌍 Real-World Applications

Resource Allocation: Budgeting, project selection
Cargo Loading: Maximize value of shipped goods
Portfolio Optimization: Select investments with constraints
Cloud Computing: VM allocation, resource scheduling
Advertising: Ad slot selection
Cryptography: Knapsack cryptosystems
Data Compression: Optimal bit allocation
Sports Drafting: Roster selection with salary cap

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic 0/1: "Given weights and values, maximize value with capacity W"
Unbounded: "You have unlimited coins of denominations, find min coins for amount"
Subset Sum: "Can you make exactly target sum?"
Partition: "Can you split array into two equal sum subsets?"
Target Sum: "Ways to assign +/- to make target sum"
Last Stone Weight: "Reduce stones by smashing equal weights"
Coin Change: "Minimum coins to make amount" (unbounded)
Combination Sum: "Find all combinations that sum to target"

# Common Interview Question Patterns:
# 1. "Find max profit" → 0/1 Knapsack
# 2. "Find if possible" → Subset Sum
# 3. "Find minimum/maximum" → DP optimization
# 4. "Find number of ways" → Counting DP

# Quick Template for 0/1 Problems:
def solve_01(items, capacity):
    dp = [0] * (capacity + 1)
    for weight, value in items:
        for w in range(capacity, weight - 1, -1):
            dp[w] = max(dp[w], dp[w - weight] + value)
    return dp[capacity]

# Template for Unbounded Problems:
def solve_unbounded(items, capacity):
    dp = [0] * (capacity + 1)
    for w in range(1, capacity + 1):
        for weight, value in items:
            if weight <= w:
                dp[w] = max(dp[w], dp[w - weight] + value)
    return dp[capacity]