Knapsack: 0/1 and Unbounded Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Knapsack: Complete Guide with 0/1 and Unbounded Examples

If you have not read the concept guide yet, start there for the intuition and the complexity analysis. This page gives you the code you can memorize and adapt during an interview. Every template here is built around the same table, with items in one direction, capacity in the other, and a decision rule at each cell.

Main Template: 0/1 Knapsack

This is the definitional version of the pattern. Each item is used at most once, and the full 2D table makes the states explicit, which matters when the interviewer asks you to walk through the recurrence out loud. The space-optimized variant below is what you actually type, but this version is what you explain. It runs in

O(N*W)

time and

O(N*W)

space.

Use this for the classic maximize-value form. The same table with boolean values solves Partition Equal Subset Sum .

function knapsack01(weights, values, capacity) {
    const n = weights.length;
    // dp[i][w] is the best value using the first i items with
    // capacity w. The extra row and column are the base cases
    // "no items" and "zero capacity", both worth zero.
    const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 0; w <= capacity; w++) {
            if (weights[i - 1] > w) {
                // The item does not fit. Copy the row above,
                // which already holds the best answer without it.
                dp[i][w] = dp[i - 1][w];
            } else {
                // Either leave the item out, or take it and add
                // the best value for the leftover capacity from
                // the previous row. The previous row guarantees
                // the item is not counted twice.
                dp[i][w] = Math.max(
                    dp[i - 1][w],
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]
                );
            }
        }
    }
    return dp[n][capacity];
}

from typing import List

def knapsack_01(weights: List[int], values: List[int], capacity: int) -> int:
    n = len(weights)
    # dp[i][w] is the best value using the first i items with
    # capacity w. Row 0 and column 0 cover the "no items" and
    # "zero capacity" base cases.
    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:
                # Item does not fit, so the previous row's answer
                # is the best we can carry.
                dp[i][w] = dp[i - 1][w]
            else:
                # Skip the item, or take it and add the best value
                # for the leftover capacity from the previous row.
                dp[i][w] = max(
                    dp[i - 1][w],
                    values[i - 1] + dp[i - 1][w - weights[i - 1]],
                )

    return dp[n][capacity]

public int knapsack01(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    // dp[i][w] is the best value using the first i items with
    // capacity w. Row 0 and column 0 are the zero-item and
    // zero-capacity base cases.
    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] = dp[i - 1][w]; // too heavy, must skip
            } else {
                dp[i][w] = Math.max(
                    dp[i - 1][w],
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]
                );
            }
        }
    }
    return dp[n][capacity];
}

#include <vector>
#include <algorithm>

int knapsack01(const std::vector<int>& weights,
               const std::vector<int>& values,
               int capacity) {
    int n = weights.size();
    // dp[i][w] is the best value using the first i items with
    // capacity w. Row 0 and column 0 are the zero-item and
    // zero-capacity base cases.
    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] = dp[i - 1][w]; // too heavy, must skip
            } else {
                dp[i][w] = std::max(
                    dp[i - 1][w],
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]
                );
            }
        }
    }
    return dp[n][capacity];
}

func knapsack01(weights, values []int, capacity int) int {
    n := len(weights)
    // dp[i][w] is the best value using the first i items with
    // capacity w. Row 0 and column 0 cover the "no items" and
    // "zero capacity" base cases.
    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 {
                // Item does not fit, so carry the previous
                // row's answer forward.
                dp[i][w] = dp[i-1][w]
            } else {
                // Compare skipping the item against taking it
                // plus the best value for the leftover capacity.
                take := values[i-1] + dp[i-1][w-weights[i-1]]
                if take > dp[i-1][w] {
                    dp[i][w] = take
                } else {
                    dp[i][w] = dp[i-1][w]
                }
            }
        }
    }
    return dp[n][capacity]
}

def knapsack_01(weights, values, capacity)
    n = weights.length
    # dp[i][w] is the best value using the first i items with
    # capacity w. Row 0 and column 0 are the zero-item and
    # zero-capacity base cases.
    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] # too heavy, must skip
            else
                dp[i][w] = [
                    dp[i - 1][w],
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]
                ].max
            end
        end
    end

    dp[n][capacity]
end

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

i: the row index, which counts items. Row 0 means no items are available. Item i in the table is the array element at weights[i-1], because the 0 slot belongs to the base case.
w: the column index, which is the capacity under consideration. Column 0 means zero capacity, so every cell in it stays 0.
dp[i][w]: the best value achievable with the first i items and exactly w capacity.
capacity: the final column and the answer location. dp[n][capacity] is the maximum value for the full item list.

Visual Mechanism

    stateDiagram-v2
    [*] --> Start: "i = 1, w = 0"
    Start --> Fit: "item weight <= w?"
    Fit --> Skip: "No"
    Fit --> Decide: "Yes"
    Decide --> Take: "value + dp[i-1][w-weight]"
    Decide --> Skip: "dp[i-1][w]"
    Take --> Next: "max of the two"
    Skip --> Next
    Next --> Start: "next cell"
    Start --> Done: "after last cell"
    Done --> [*]

Critical Sections

The initialization builds a table with an empty row and an empty column. That one decision removes every boundary check. When there are no items, every cell is 0, and when capacity is 0, every cell is 0. Without the padding you would need if guards on both indices, which is where off-by-one errors creep in.

The transition is the whole pattern. The skip branch copies the cell above, which already holds the best answer without the current item. The take branch looks one row up and weights[i-1] columns left. Reading from the previous row is what makes the item count at most once. If the take branch read from the current row, an item could be used twice in a single row.

The answer is the bottom-right cell, not the bottom row or the right column. Those other cells are real answers for smaller item sets or smaller capacities, but only the corner cell considers every item with the full budget.

Variations

1. Space-Optimized 0/1 Knapsack

The 2D table exists only because each row needs the row above it. A single array can be overwritten in place, cutting space from

O(N*W)

O(W)

. The cost is that capacity must now be iterated backward.

Use this for Partition Equal Subset Sum .

function knapsack01Optimized(weights, values, capacity) {
    const dp = new Array(capacity + 1).fill(0);

    for (let i = 0; i < weights.length; i++) {
        // Walk capacity downward. A forward loop would read
        // dp[w - weights[i]] after it was already updated with
        // the current item, letting the item be used twice.
        for (let w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }
    return dp[capacity];
}

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

    for i in range(len(weights)):
        # Iterate w downward. Reading dp[w - weights[i]] from the
        # left would use the current item's updates, which lets
        # the item be taken more than once.
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])

    return dp[capacity]

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

    for (int i = 0; i < weights.length; i++) {
        // Capacity must run downward so the cell just read
        // still holds the previous item's value.
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }
    return dp[capacity];
}

#include <vector>
#include <algorithm>

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++) {
        // Walk capacity down so dp[w - weights[i]] still holds
        // the value from the previous item, not the current one.
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = std::max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }
    return dp[capacity];
}

func knapsack01Optimized(weights, values []int, capacity int) int {
    dp := make([]int, capacity+1)

    for i := 0; i < len(weights); i++ {
        // Iterate capacity downward. The slot read on the left
        // must come from the previous item, so it cannot have
        // been updated by the current one yet.
        for w := capacity; w >= weights[i]; w-- {
            take := values[i] + dp[w-weights[i]]
            if take > dp[w] {
                dp[w] = take
            }
        }
    }
    return dp[capacity]
}

def knapsack_01_optimized(weights, values, capacity)
    dp = Array.new(capacity + 1, 0)

    weights.each_with_index do |weight, i|
        # Walking capacity downward keeps dp[w - weight] on the
        # previous item's value, so the item is not reused.
        capacity.downto(weight) do |w|
            dp[w] = [dp[w], values[i] + dp[w - weight]].max
        end
    end

    dp[capacity]
end

2. Unbounded Knapsack: Count Ways

When every item can be used any number of times, the capacity loop flips direction. Walking forward lets each update feed into later updates in the same pass, which is exactly the reuse the 0/1 version has to prevent. This variation counts combinations, so the table holds counts instead of values and dp[0] starts at 1 for the empty combination. It runs in

O(N*A)

time and

O(A)

space, where A is the target amount.

Use this for Coin Change II .

function change(amount, coins) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1; // one way to make zero: pick no coins

    for (const coin of coins) {
        // Forward loop so a coin can be added to sums that
        // already used the same coin in this pass.
        for (let a = coin; a <= amount; a++) {
            dp[a] += dp[a - coin];
        }
    }
    return dp[amount];
}

def change(amount: int, coins: List[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1  # one way to make zero: pick no coins

    for coin in coins:
        # Walk forward so each coin can extend sums that were
        # just built with the same coin.
        for a in range(coin, amount + 1):
            dp[a] += dp[a - coin]

    return dp[amount]

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1; // one way to make zero: pick no coins

    for (int coin : coins) {
        // Forward pass lets the same coin repeat within
        // one coin's loop, which is the unbounded behavior.
        for (int a = coin; a <= amount; a++) {
            dp[a] += dp[a - coin];
        }
    }
    return dp[amount];
}

#include <vector>

int change(int amount, const std::vector<int>& coins) {
    std::vector<int> dp(amount + 1, 0);
    dp[0] = 1; // one way to make zero: pick no coins

    for (int coin : coins) {
        // Forward pass, so sums built earlier in this coin's
        // loop can be extended again with the same coin.
        for (int a = coin; a <= amount; a++) {
            dp[a] += dp[a - coin];
        }
    }
    return dp[amount];
}

func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1 // one way to make zero: pick no coins

    for _, coin := range coins {
        // Forward pass, so a coin can be added to sums that
        // already used it earlier in this same pass.
        for a := coin; a <= amount; a++ {
            dp[a] += dp[a-coin]
        }
    }
    return dp[amount]
}

3. Subset Sum: Boolean Table

When the question is “can some subset reach this exact sum”, the values and weights collapse into one array. The table stores booleans and the transition is an OR. The target is reachable if it was reachable before this number, or if it was reachable minus this number. The backward loop stays, because each number is still usable at most once. This variation runs in

O(N*T)

time and

O(T)

space, where T is the target sum.

Use this for Partition Equal Subset Sum , where the target is half the total sum.

function canPartition(nums) {
    const total = nums.reduce((a, b) => a + b, 0);
    if (total % 2 !== 0) return false;

    const target = total / 2;
    const dp = new Array(target + 1).fill(false);
    dp[0] = true; // the empty subset sums to zero

    for (const num of nums) {
        // Backward loop keeps each number usable once.
        for (let s = target; s >= num; s--) {
            dp[s] = dp[s] || dp[s - num];
        }
    }
    return dp[target];
}

def can_partition(nums: List[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False

    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True  # the empty subset sums to zero

    for num in nums:
        # Backward loop, so each number is used at most once.
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

public boolean canPartition(int[] nums) {
    int total = 0;
    for (int num : nums) total += num;
    if (total % 2 != 0) return false;

    int target = total / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true; // the empty subset sums to zero

    for (int num : nums) {
        // Backward loop keeps each number usable once.
        for (int s = target; s >= num; s--) {
            dp[s] = dp[s] || dp[s - num];
        }
    }
    return dp[target];
}

#include <vector>
#include <numeric>

bool canPartition(const std::vector<int>& nums) {
    int total = std::accumulate(nums.begin(), nums.end(), 0);
    if (total % 2 != 0) return false;

    int target = total / 2;
    std::vector<bool> dp(target + 1, false);
    dp[0] = true; // the empty subset sums to zero

    for (int num : nums) {
        // Backward loop, so each number is used at most once.
        for (int s = target; s >= num; s--) {
            dp[s] = dp[s] || dp[s - num];
        }
    }
    return dp[target];
}

func canPartition(nums []int) bool {
    total := 0
    for _, num := range nums {
        total += num
    }
    if total%2 != 0 {
        return false
    }

    target := total / 2
    dp := make([]bool, target+1)
    dp[0] = true // the empty subset sums to zero

    for _, num := range nums {
        // Backward loop keeps each number usable once.
        for s := target; s >= num; s-- {
            if dp[s-num] {
                dp[s] = true
            }
        }
    }
    return dp[target]
}

def can_partition(nums)
    total = nums.sum
    return false if total.odd?

    target = total / 2
    dp = Array.new(target + 1, false)
    dp[0] = true # the empty subset sums to zero

    nums.each do |num|
        # Backward loop, so each number is used at most once.
        target.downto(num) do |s|
            dp[s] = dp[s] || dp[s - num]
        end
    end

    dp[target]
end

For the minimizing variant, the unbounded template changes two things: dp starts at infinity instead of zero, and the transition takes a min instead of adding counts. You can see the full version in Coin Change on the problems page.

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .