The Knapsack Problem: A Comprehensive Guide to Dynamic Programming

def knapsack_01_2d(max_weight: int, weights: list[int], values: list[int]) -> int:
    """
    Solves the 0/1 Knapsack Problem using a 2D DP table.
    """
    n = len(values)
    
    # Initialize a 2D DP matrix with dimensions (n+1) x (max_weight+1)
    # Pre-filled with mostly zeros
    dp = [[0 for _ in range(max_weight + 1)] for _ in range(n + 1)]

    # Build table in bottom-up manner
    for i in range(1, n + 1):
        for w in range(1, max_weight + 1):
            
            item_weight = weights[i-1]
            item_value = values[i-1]
            
            if item_weight <= w:
                # We have enough capacity to potentially take the item
                # Max of (NOT taking it) vs (TAKING it + value of leftover space)
                dp[i][w] = max(
                    dp[i-1][w],
                    item_value + dp[i-1][w - item_weight]
                )
            else:
                # The item is too heavy for the current running capacity 'w'.
                # We HAVE to exclude it and inherit the previous state.
                dp[i][w] = dp[i-1][w]

    # The final cell in the bottom-right corner holds the maximum profit
    return dp[n][max_weight]


# Usage Example
items = ["Guitar", "Keyboard", "Accordion"]
values = [1500, 3000, 2000]
weights = [1, 4, 3]
max_capacity = 4

max_profit = knapsack_01_2d(max_capacity, weights, values)
print(f"Maximum Profit: ${max_profit}")
# => Maximum Profit: $3500 (Takes Guitar + Accordion)
```python
---

## Complexity Analysis

### Time Complexity: $O(N \times W)$

Where `N` is the total number of distinct items, and `W` is the maximum weight capacity of the knapsack. Because we must iterate through and populate an entire matrix of this size, the algorithm executes in pseudo-polynomial time.

### Space Complexity: $O(N \times W)$ (Unoptimized)

Because we construct a 2D array, we consume memory proportional to the number of items multiplied by the weight. For massive knapsacks (e.g., a capacity of 100,000 lbs), this 2D array could hit memory limits locally.

---

## Space Optimization (1D Array Trick)

If you revisit the State Transition Equation carefully:
`DP[i][w] = max( DP[i-1][w], Value_i + DP[i-1][w - Weight_i] )`

You will notice that calculating row `i` **strictly only requires data from row `i-1`**. We don't need row `i-2`, `i-3`, etc. We can discard historical rows.

Even better: if we iterate through the capacities **backwards** (from `max_capacity` down to `0`), we can squash the entire 2D matrix into a single flat `1D` array of size `W`. Iterating backwards guarantees we are reading the `i-1` state from the left side of the array before we overwrite it with the fresh `i` calculation.

### Optimized Implementation in Go

This is the production-ready 1D optimized variant, cutting Space Complexity violently down from $O(N \times W)$ to merely **$O(W)$**.

```go
package main

import (
"fmt"
)

// max returns the larger of two ints
func max(a, b int) int {
if a > b {
return a
}
return b
}

// Knapsack1D solves 0/1 Knapsack with O(W) space
func Knapsack1D(capacity int, weights []int, values []int) int {
n := len(values)

// Create a single 1D slice spanning 0 to capacity
dp := make([]int, capacity+1)

// Iterate over every item
for i := 0; i < n; i++ {
// Iterate BACKWARDS through capacities
// Crucial: we stop as soon as w < weights[i] because we can't fit it anyway
for w := capacity; w >= weights[i]; w-- {
dp[w] = max(
dp[w],                           // Case 1: Exclude item
values[i] + dp[w-weights[i]],    // Case 2: Include item
)
}
}

return dp[capacity]
}

func main() {
values := []int{1500, 3000, 2000}
weights := []int{1, 4, 3}
capacity := 4

profit := Knapsack1D(capacity, weights, values)
fmt.Printf("Optimized 1D Maximum Profit: $%d\n", profit)
// => Optimized 1D Maximum Profit: $3500
}

def knapsack_ruby(max_weight, goods)
  # goods = [[value, weight], [value, weight]]
  
  # Initialize 2D matrix
  dp = Array.new(goods.size + 1) { Array.new(max_weight + 1, 0) }
  
  (1..goods.size).each do |i|
    item_val = goods[i-1][0]
    item_wt = goods[i-1][1]
    
    (1..max_weight).each do |w|
      if item_wt <= w
        dp[i][w] = [ 
          dp[i-1][w], 
          item_val + dp[i-1][w - item_wt] 
        ].max
      else
        dp[i][w] = dp[i-1][w]
      end
    end
  end
  
  dp[goods.size][max_weight]
end

goods = [ [1500, 1], [3000, 4], [2000, 3] ]
puts knapsack_ruby(4, goods)

def unbounded_knapsack(max_weight: int, weights: list[int], values: list[int]) -> int:
    """Unbounded knapsack: each item can be used multiple times."""
    dp = [0] * (max_weight + 1)

    for w in range(1, max_weight + 1):
        for i in range(len(weights)):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[max_weight]


# Example: coin change (minimize coins for target amount)
def coin_change(coins: list[int], amount: int) -> int:
    """Minimum number of coins to make amount (unbounded)."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] = min(dp[a], dp[a - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

def fractional_knapsack(max_weight: float, weights: list[float], values: list[float]) -> float:
    """Fractional knapsack: greedy by value/weight ratio."""
    items = [(values[i], weights[i], values[i] / weights[i]) for i in range(len(weights))]
    items.sort(key=lambda x: x[2], reverse=True)  # Sort by ratio descending

    total_value = 0.0
    remaining = max_weight

    for value, weight, ratio in items:
        if weight <= remaining:
            total_value += value
            remaining -= weight
        else:
            total_value += ratio * remaining
            break

    return total_value


# Example: resource allocation
items_value = [60, 100, 120]
items_weight = [10, 20, 30]
capacity = 50
print(f"Maximum fractional value: {fractional_knapsack(capacity, items_weight, items_value)}")
# => Maximum fractional value: 240.0

def bounded_knapsack(max_weight: int, weights: list[int], values: list[int], counts: list[int]) -> int:
    """Bounded knapsack: each item available in limited quantity."""
    n = len(weights)
    dp = [0] * (max_weight + 1)

    for i in range(n):
        # Binary splitting: decompose count into powers of 2
        remaining = counts[i]
        k = 1
        while remaining > 0:
            take = min(k, remaining)
            w = weights[i] * take
            v = values[i] * take

            # 0/1 knapsack for this combined item
            for capacity in range(max_weight, w - 1, -1):
                dp[capacity] = max(dp[capacity], dp[capacity - w] + v)

            remaining -= take
            k <<= 1  # Double: 1, 2, 4, 8, ...

    return dp[max_weight]


# Example
weights = [2, 3, 5]
values = [10, 15, 25]
counts = [3, 2, 1]
print(f"Bounded knapsack max: {bounded_knapsack(10, weights, values, counts)}")

def multi_dimensional_knapsack(
    capacities: list[int],
    weights: list[list[int]],
    values: list[int]
) -> int:
    """Knapsack with multiple resource constraints."""
    dims = len(capacities)
    n = len(values)

    size = tuple(c + 1 for c in capacities)
    dp = np.zeros(size, dtype=int)

    # Simplified 2D version:
    if dims == 2:
        for i in range(n):
            for w in range(capacities[0], weights[i][0] - 1, -1):
                for v in range(capacities[1], weights[i][1] - 1, -1):
                    dp[w][v] = max(dp[w][v],
                                   dp[w - weights[i][0]][v - weights[i][1]] + values[i])

    return dp[tuple(capacities)]


# 2D example: weight and volume constraints
max_weight = 10
max_volume = 15
items_weights = [[5, 3], [4, 8], [7, 4], [3, 5]]
items_values = [50, 60, 70, 30]
print(multi_dimensional_knapsack([max_weight, max_volume], items_weights, items_values))

def subset_sum(nums: list[int], target: int) -> bool:
    """Check if any subset sums to target."""
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(target, num - 1, -1):
            if dp[s - num]:
                dp[s] = True

    return dp[target]


def subset_sum_count(nums: list[int], target: int) -> int:
    """Count subsets that sum to target."""
    dp = [0] * (target + 1)
    dp[0] = 1

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

    return dp[target]


# Testing
nums = [3, 34, 4, 12, 5, 2]
print(f"Subset sum to 9: {subset_sum(nums, 9)}")     # True (4+5 or 3+4+2)
print(f"Subset sum to 30: {subset_sum(nums, 30)}")   # False
print(f"Subset sum count to 9: {subset_sum_count(nums, 9)}")  # 2

import unittest

class TestKnapsack(unittest.TestCase):
    def test_01_knapsack(self):
        weights = [1, 4, 3]
        values = [1500, 3000, 2000]
        self.assertEqual(knapsack_01_2d(4, weights, values), 3500)
        self.assertEqual(Knapsack1D(4, weights, values), 3500)

    def test_unbounded(self):
        weights = [1, 3, 4]
        values = [15, 50, 60]
        self.assertEqual(unbounded_knapsack(8, weights, values), 120)

    def test_fractional(self):
        weights = [10, 20, 30]
        values = [60, 100, 120]
        self.assertAlmostEqual(fractional_knapsack(50, weights, values), 240.0)

    def test_subset_sum(self):
        self.assertTrue(subset_sum([3, 34, 4, 12, 5, 2], 9))
        self.assertFalse(subset_sum([3, 34, 4, 12, 5, 2], 30))

    def test_edge_cases(self):
        self.assertEqual(knapsack_01_2d(0, [1, 2], [10, 20]), 0)
        self.assertEqual(knapsack_01_2d(5, [], []), 0)
        self.assertEqual(unbounded_knapsack(0, [1, 2], [10, 20]), 0)

if __name__ == '__main__':
    unittest.main()