Coding Patterns
Knapsack
Code Templates

Code Templates

Master the knapsack problem with these optimized code templates. Use them as starting points for solving various knapsack variations across different programming languages. For a conceptual overview, check out the Knapsack Guide.

When to Use Knapsack Templates

Knapsack algorithms are your go-to solution for optimization and subset selection problems where you need to:

  • Maximize value or minimize cost with constraints
  • Choose items with weights and values
  • Find combinations that meet target sums
  • Solve partition, subset sum, or coin change problems

Key Characteristics:

  • Discrete choices (take or don’t take) for 0/1 knapsack
  • Unlimited repetition allowed for unbounded knapsack
  • O(N*W)
    time     with
    O(N*W)
    or
    O(W)
    space
  • Optimal substructure - optimal solution contains optimal solutions to subproblems

Common Applications:

  • Resource allocation problems
  • Budget optimization
  • Subset sum and partition problems
  • Coin change and combination counting
  • Multi-constraint selection (ones and zeroes)

0/1 Knapsack - Maximize Value

The classic 0/1 knapsack problem where each item can be used at most once. This is the foundation for all knapsack variations.

When to Use:

  • Items have weights and values
  • Each item can be chosen at most once
  • Need to maximize total value within capacity constraint
  • Subset selection problems

Key Insight: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight] + value) - either exclude or include the current item.

JavaScript:

/**
 * 0/1 Knapsack - Maximize value with weight constraint
 * @param {number[]} weights - Array of item weights
 * @param {number[]} values - Array of item values
 * @param {number} capacity - Knapsack capacity
 * @returns {number} Maximum value achievable
 */
function knapsack01(weights, values, capacity) {
    const n = weights.length;
    const dp = Array(n + 1).fill().map(() => Array(capacity + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 0; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                    dp[i - 1][w],                                    // Exclude item
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]   // Include item
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}

Python:

from typing import List

def knapsack_01(weights: List[int], values: List[int], capacity: int) -> int:
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    dp[i - 1][w],                                    # Exclude item
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]   # Include item
                )
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

Java:

public class Knapsack {
    /**
     * 0/1 Knapsack - Maximize value with weight constraint
     */
    public int knapsack01(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(
                        dp[i - 1][w],                                    // Exclude item
                        values[i - 1] + dp[i - 1][w - weights[i - 1]]   // Include item
                    );
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][capacity];
    }
}

C++:

#include <vector>
#include <algorithm>

class Knapsack {
public:
    /**
     * 0/1 Knapsack - Maximize value with weight constraint
     */
    int knapsack01(const std::vector<int>& weights,
                  const std::vector<int>& values,
                  int capacity) {
        int n = weights.size();
        std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));

        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = std::max(
                        dp[i - 1][w],                                    // Exclude item
                        values[i - 1] + dp[i - 1][w - weights[i - 1]]   // Include item
                    );
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][capacity];
    }
};

Go:

// 0/1 Knapsack - Maximize value with weight constraint
func Knapsack01(weights, values []int, capacity int) int {
    n := len(weights)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }

    for i := 1; i <= n; i++ {
        for w := 0; w <= capacity; w++ {
            if weights[i-1] <= w {
                dp[i][w] = max(
                    dp[i-1][w],                                    // Exclude item
                    values[i-1]+dp[i-1][w-weights[i-1]],           // Include item
                )
            } else {
                dp[i][w] = dp[i-1][w]
            }
        }
    }

    return dp[n][capacity]
}

Ruby:

# 0/1 Knapsack - Maximize value with weight constraint
def knapsack_01(weights, values, capacity)
  n = weights.length
  dp = Array.new(n + 1) { Array.new(capacity + 1, 0) }

  (1..n).each do |i|
    (0..capacity).each do |w|
      if weights[i - 1] <= w
        dp[i][w] = [
          dp[i - 1][w],                                    # Exclude item
          values[i - 1] + dp[i - 1][w - weights[i - 1]]   # Include item
        ].max
      else
        dp[i][w] = dp[i - 1][w]
      end
    end
  end

  dp[n][capacity]
end

0/1 Knapsack - Space Optimized

Optimized version using 1D array instead of 2D table. Reduces space complexity from

O(N*W)
to
O(W)
.

Key Change: Iterate backwards on capacity to prevent reusing the same item multiple times.

JavaScript:

/**
 * Space-optimized 0/1 knapsack using 1D array
 */
function knapsack01Optimized(weights, values, capacity) {
    const dp = new Array(capacity + 1).fill(0);

    for (let i = 0; i < weights.length; i++) {
        // Iterate backwards to avoid using same item twice
        for (let w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }

    return dp[capacity];
}

Python:

def knapsack_01_optimized(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)

    for i in range(len(weights)):
        # Iterate backwards to avoid using same item twice
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])

    return dp[capacity]

Java:

public int knapsack01Optimized(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];

    for (int i = 0; i < weights.length; i++) {
        // Iterate backwards to avoid using same item twice
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }

    return dp[capacity];
}

C++:

int knapsack01Optimized(const std::vector<int>& weights,
                       const std::vector<int>& values,
                       int capacity) {
    std::vector<int> dp(capacity + 1, 0);

    for (size_t i = 0; i < weights.size(); i++) {
        // Iterate backwards to avoid using same item twice
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = std::max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }

    return dp[capacity];
}

Go:

// Space-optimized 0/1 knapsack using 1D array
func Knapsack01Optimized(weights, values []int, capacity int) int {
    dp := make([]int, capacity+1)

    for i := 0; i < len(weights); i++ {
        // Iterate backwards to avoid using same item twice
        for w := capacity; w >= weights[i]; w-- {
            dp[w] = max(dp[w], values[i]+dp[w-weights[i]])
        }
    }

    return dp[capacity]
}

Ruby:

# Space-optimized 0/1 knapsack using 1D array
def knapsack_01_optimized(weights, values, capacity)
  dp = Array.new(capacity + 1, 0)

  weights.each_with_index do |weight, i|
    # Iterate backwards to avoid using same item twice
    (capacity).downto(weight).each do |w|
      dp[w] = [dp[w], values[i] + dp[w - weight]].max
    end
  end

  dp[capacity]
end

Unbounded Knapsack - Count Ways (Coin Change 2)

Count the number of ways to make up a target amount using unlimited coins.

When to Use:

  • Unlimited quantity of each item
  • Count combinations, not just maximum value
  • Coin change, combination problems

Key Insight: For each coin, update dp from coin to amount. Iterate forward to allow unlimited use.

JavaScript:

/**
 * Count combinations to make amount (Coin Change 2)
 * @param {number[]} coins - Coin denominations
 * @param {number} amount - Target amount
 * @returns {number} Number of combinations
 */
function coinChange2(coins, amount) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1; // One way to make 0

    for (const coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

Python:

from typing import List

def coin_change_2(coins: List[int], amount: int) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to make 0

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

    return dp[amount]

Java:

public class CoinChange {
    /**
     * Count combinations to make amount
     */
    public int coinChange2(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1; // One way to make 0

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }
}

C++:

#include <vector>

class CoinChange {
public:
    int coinChange2(const std::vector<int>& coins, int amount) {
        std::vector<int> dp(amount + 1, 0);
        dp[0] = 1; // One way to make 0

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }
};

Go:

// Count combinations to make amount (Coin Change 2)
func CoinChange2(coins []int, amount int) int {
    dp := make([]int, amount+1)
    dp[0] = 1 // One way to make 0

    for _, coin := range coins {
        for i := coin; i <= amount; i++ {
            dp[i] += dp[i-coin]
        }
    }

    return dp[amount]
}

Ruby:

# Count combinations to make amount (Coin Change 2)
def coin_change_2(coins, amount)
  dp = Array.new(amount + 1, 0)
  dp[0] = 1 # One way to make 0

  coins.each do |coin|
    (coin..amount).each do |i|
      dp[i] += dp[i - coin]
    end
  end

  dp[amount]
end

Unbounded Knapsack - Minimum Coins (Coin Change 1)

Find the minimum number of coins needed to make up a target amount.

When to Use:

  • Minimize number of items to reach target
  • Unlimited quantity of each item available
  • Return -1 if impossible

Key Insight: Initialize dp with Infinity (except dp[0] = 0). Use min instead of max.

JavaScript:

/**
 * Minimum coins to make amount (Coin Change 1)
 * @param {number[]} coins - Coin denominations
 * @param {number} amount - Target amount
 * @returns {number} Minimum coins or -1 if impossible
 */
function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0; // Base case

    for (const coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

Python:

from typing import List

def coin_change(coins: List[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case

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

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

Java:

public class CoinChange {
    /**
     * Minimum coins to make amount
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0; // Base case

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                if (dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

C++:

#include <vector>
#include <climits>

class CoinChange {
public:
    int coinChange(const std::vector<int>& coins, int amount) {
        std::vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0; // Base case

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                if (dp[i - coin] != INT_MAX) {
                    dp[i] = std::min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

Go:

import "math"

// Minimum coins to make amount (Coin Change 1)
func CoinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        dp[i] = math.MaxInt32
    }
    dp[0] = 0 // Base case

    for _, coin := range coins {
        for i := coin; i <= amount; i++ {
            if dp[i-coin] != math.MaxInt32 {
                dp[i] = min(dp[i], dp[i-coin]+1)
            }
        }
    }

    if dp[amount] == math.MaxInt32 {
        return -1
    }
    return dp[amount]
}

Ruby:

# Minimum coins to make amount (Coin Change 1)
def coin_change(coins, amount)
  dp = Array.new(amount + 1, Float::INFINITY)
  dp[0] = 0 # Base case

  coins.each do |coin|
    (coin..amount).each do |i|
      dp[i] = [dp[i], dp[i - coin] + 1].min
    end
  end

  dp[amount] == Float::INFINITY ? -1 : dp[amount]
end

Multi-Dimensional Knapsack (Ones and Zeroes)

2D knapsack with two constraints (zeros and ones budget).

When to Use:

  • Multiple constraints (weight, volume, count, etc.)
  • LeetCode 474: Ones and Zeroes
  • Problems with limited resources

JavaScript:

/**
 * Multi-dimensional knapsack with two constraints
 * @param {string[]} strs - Array of binary strings
 * @param {number} m - Zero budget
 * @param {number} n - One budget
 * @returns {number} Maximum subset size
 */
function findMaxForm(strs, m, n) {
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    for (const str of strs) {
        let zeros = 0, ones = 0;
        for (const char of str) {
            if (char === '0') zeros++;
            else ones++;
        }

        // Update dp table backwards
        for (let i = m; i >= zeros; i--) {
            for (let j = n; j >= ones; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
            }
        }
    }

    return dp[m][n];
}

Python:

from typing import List

def find_max_form(strs: List[str], m: int, n: int) -> int:
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for s in strs:
        zeros = s.count('0')
        ones = len(s) - zeros

        for i in range(m, zeros - 1, -1):
            for j in range(n, ones - 1, -1):
                dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)

    return dp[m][n]

Java:

public class OnesAndZeroes {
    /**
     * Multi-dimensional knapsack with two constraints
     */
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        for (String s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s.toCharArray()) {
                if (c == '0') zeros++;
                else ones++;
            }

            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }

        return dp[m][n];
    }
}

C++:

#include <vector>
#include <string>
#include <algorithm>

class OnesAndZeroes {
public:
    int findMaxForm(const std::vector<std::string>& strs, int m, int n) {
        std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

        for (const std::string& s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s) {
                if (c == '0') zeros++;
                else ones++;
            }

            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = std::max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }

        return dp[m][n];
    }
};

Go:

import "strings"

// Multi-dimensional knapsack with two constraints
func FindMaxForm(strs []string, m, n int) int {
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for _, s := range strs {
        zeros := strings.Count(s, "0")
        ones := len(s) - zeros

        for i := m; i >= zeros; i-- {
            for j := n; j >= ones; j-- {
                dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)
            }
        }
    }

    return dp[m][n]
}

Ruby:

# Multi-dimensional knapsack with two constraints
def find_max_form(strs, m, n)
  dp = Array.new(m + 1) { Array.new(n + 1, 0) }

  strs.each do |s|
    zeros = s.count('0')
    ones = s.length - zeros

    (m).downto(zeros).each do |i|
      (n).downto(ones).each do |j|
        dp[i][j] = [dp[i][j], dp[i - zeros][j - ones] + 1].max
      end
    end
  end

  dp[m][n]
end

Code Breakdown

The 0/1 knapsack template relies on these key components:

1. The DP Table (dp)

  • 2D array of size (N+1) x (W+1) where N = number of items, W = capacity
  • dp[0][w] = 0 for all w - no items available means zero value
  • dp[i][w] represents maximum value using first i items with capacity w

2. State Transition Formula 

dp[i][w] = max(
    dp[i-1][w],                              // Exclude item i-1
    values[i-1] + dp[i-1][w-weights[i-1]]    // Include item i-1
)
  • Exclude: Same value as previous row without this item
  • Include: Item value + best value for remaining capacity from previous row

3. Iteration Direction 

  graph LR
   subgraph Items[Process Items]
       A[Item 1] --> B[Item 2] --> C[Item N]
   end
   
   subgraph ZeroOne[0/1 Knapsack]
       Dir01[W to weight]
       Result01[Use item once]
   end
   
   subgraph Unbounded[Unbounded Knapsack]
       DirUnbounded[weight to W]
       ResultUnbounded[Reuse allowed]
   end
   
   Items --> ZeroOne
   Items --> Unbounded
   
   style Dir01 fill:#aaf,stroke:#333
   style DirUnbounded fill:#f9d,stroke:#333

4. Space Optimization

  • 2D to 1D: Instead of storing full table, use single array of size W+1
  • Backward iteration: For 0/1 knapsack, iterate from W down to weight[i]
    • This prevents using the same item multiple times
    • When iterating forward, dp[w - weight[i]] may already include current item
  • Forward iteration: For unbounded knapsack, iterate from weight[i] up to W
    • Allows unlimited reuse of the same item

Next Steps

Now that you have templates, it’s time to apply them. Head over to the Practice Problems page to solve real LeetCode challenges using these patterns.