Back to Technology

Advanced Knapsack & Coin Change Variants

September 9, 2026 Wasil Zafar 24 min read

Beyond 0/1 and unbounded knapsack lie six variants that keep showing up in real systems and interviews: bounded supply, multiple bins, exact-sum reachability, equal partitions, order-sensitive counting, and coins with limited stock.

Table of Contents

  1. Introduction and Motivation
  2. Prerequisites
  3. Bounded Knapsack and Multiple Knapsack
  4. Subset Sum and Partition
  5. Ordered Compositions and Bounded Coins
  6. A Note on Bitset Optimization
  7. Complexity Comparison Table
  8. Applications and Alternatives
  9. Exercises and Mastery
  10. Summary Cheat Sheet
Mastery target: Level B implementation. You should be able to pick the right knapsack/coin-change variant for a stated constraint, justify the loop order or reduction that makes it work, and implement it without notes.

1. Introduction and Motivation

0/1 Knapsack and Unbounded Knapsack cover the two extremes of item availability: take an item once, or take it as many times as capacity allows. Coin Change covers the two questions usually asked of an unbounded knapsack: what is the minimum count needed, and how many ways exist to hit a target. Real problems rarely sit at either extreme. A warehouse has a limited stock of each SKU, not one unit and not infinite units. A vending machine has a bounded number of each coin, not a mint. A logistics run has several trucks, not one bag. And some counting questions care about the order in which choices happen, not just which choices happen.

This lesson covers exactly the variants that fill those gaps: Bounded Knapsack, Multiple Knapsack, Subset Sum, Partition Equal Subset Sum, Ordered Compositions, and Bounded Coins. Each one reuses a DP skeleton you already know — the difference is a changed state, a reordered loop, or a reduction trick (binary grouping) that turns a hard bounded problem into an easy 0/1 problem.

2. Prerequisites

This lesson assumes you have already worked through 0/1 Knapsack and Unbounded Knapsack and both Coin Change variants — minimum coins and number of ways — in Part 15: Core DP Patterns. Specifically, you should already be comfortable with:

  • Why 0/1 Knapsack traverses capacity backwards and Unbounded Knapsack traverses it forwards.
  • The coin_change minimum-coins recurrence, $dp[a] = \min(dp[a-coin]+1)$.
  • The coin_change_ways recurrence with coins in the outer loop.

None of that is re-derived here. Every section below either extends one of those four algorithms with a new constraint, or contrasts it with a variant that changes exactly one design decision.

3. Bounded Knapsack

Core insight: each item $i$ now has a maximum available count $c_i$ — not 0-or-1, not unlimited. A naive approach tries every count from $0$ to $c_i$ for every item at every capacity, giving $O(n \cdot W \cdot \max(c_i))$ time. Binary grouping instead splits item $i$ into $O(\log c_i)$ "super-items" of sizes $1, 2, 4, \dots$ plus one leftover remainder, then solves a single 0/1 Knapsack over all super-items in $O(n \cdot W \cdot \log(\max c_i))$.

Why grouping works: choosing a subset of the super-items for a given original item is equivalent to choosing how many physical copies of that item to take. The greedy split — take $\min(k, \text{remaining})$ copies where $k$ doubles each round — guarantees every count from $0$ to $c_i$ is reachable as the sum of some subset of the resulting group sizes. Once every item is replaced by its super-items, each super-item behaves like an ordinary 0/1 item: a weight of (group size × unit weight) and a value of (group size × unit value).

Count $c_i$Groups producedSuper-items
31, 22
51, 2, 23
61, 2, 33
71, 2, 43

Notice count 5 does not decompose as the "textbook" $1, 2, 2^{k-1}$ powers-of-two-only scheme; the last group is whatever remains once the running total would otherwise exceed $c_i$. That is exactly what keeps the algorithm correct for any count, not just counts that are one less than a power of two.

def bounded_knapsack(weights, values, counts, capacity):
    """
    Bounded Knapsack: item i is available at most counts[i] times.
    Binary grouping splits each item into O(log counts[i]) "super-items"
    of sizes 1, 2, 4, ... plus a leftover remainder, then solves 0/1 Knapsack.
    Time: O(n * capacity * log(max(counts))), Space: O(capacity)
    """
    super_weights = []
    super_values = []
    for w, v, c in zip(weights, values, counts):
        k = 1
        remaining = c
        while remaining > 0:
            take = min(k, remaining)
            super_weights.append(w * take)
            super_values.append(v * take)
            remaining -= take
            k *= 2

    dp = [0] * (capacity + 1)
    for sw, sv in zip(super_weights, super_values):
        # 0/1 Knapsack backward pass, exactly like Part 15 -- each
        # super-item is used at most once.
        for cap in range(capacity, sw - 1, -1):
            dp[cap] = max(dp[cap], dp[cap - sw] + sv)
    return dp[capacity]

# Example
weights = [4, 6, 5]
values = [10, 12, 9]
counts = [3, 2, 4]      # item 0 available x3, item 1 x2, item 2 x4
capacity = 20

print(f"Bounded Knapsack: {bounded_knapsack(weights, values, counts, capacity)}")  # 44

// Bounded Knapsack via binary grouping
#include <vector>
#include <algorithm>
#include <iostream>

int boundedKnapsack(const std::vector<int>& weights, const std::vector<int>& values,
                     const std::vector<int>& counts, int capacity) {
    std::vector<int> superWeights;
    std::vector<int> superValues;

    for (std::size_t i = 0; i < weights.size(); ++i) {
        int k = 1;
        int remaining = counts[i];
        while (remaining > 0) {
            int take = std::min(k, remaining);
            superWeights.push_back(weights[i] * take);
            superValues.push_back(values[i] * take);
            remaining -= take;
            k *= 2;
        }
    }

    std::vector<int> dp(capacity + 1, 0);
    for (std::size_t s = 0; s < superWeights.size(); ++s) {
        int sw = superWeights[s];
        int sv = superValues[s];
        for (int cap = capacity; cap >= sw; --cap) {
            dp[cap] = std::max(dp[cap], dp[cap - sw] + sv);
        }
    }
    return dp[capacity];
}

int main() {
    std::vector<int> weights{4, 6, 5};
    std::vector<int> values{10, 12, 9};
    std::vector<int> counts{3, 2, 4};
    int capacity = 20;
    std::cout << "Bounded Knapsack: " << boundedKnapsack(weights, values, counts, capacity) << '\n'; // 44
}

// Bounded Knapsack via binary grouping
import java.util.*;

public class BoundedKnapsack {
    static int boundedKnapsack(int[] weights, int[] values, int[] counts, int capacity) {
        List<Integer> superWeights = new ArrayList<>();
        List<Integer> superValues = new ArrayList<>();

        for (int i = 0; i < weights.length; i++) {
            int k = 1;
            int remaining = counts[i];
            while (remaining > 0) {
                int take = Math.min(k, remaining);
                superWeights.add(weights[i] * take);
                superValues.add(values[i] * take);
                remaining -= take;
                k *= 2;
            }
        }

        int[] dp = new int[capacity + 1];
        for (int s = 0; s < superWeights.size(); s++) {
            int sw = superWeights.get(s);
            int sv = superValues.get(s);
            for (int cap = capacity; cap >= sw; cap--) {
                dp[cap] = Math.max(dp[cap], dp[cap - sw] + sv);
            }
        }
        return dp[capacity];
    }

    public static void main(String[] args) {
        int[] weights = {4, 6, 5};
        int[] values = {10, 12, 9};
        int[] counts = {3, 2, 4};
        int capacity = 20;
        System.out.println("Bounded Knapsack: " + boundedKnapsack(weights, values, counts, capacity)); // 44
    }
}

Multiple Knapsack

Multiple Knapsack generalizes further: instead of one bag, there are several bins, each with its own capacity, and every item may go into at most one bin (or be left out). Deciding the optimal assignment across many bins is NP-hard in general — it combines bin packing with knapsack selection. For a small, fixed number of bins, an exact DP is still practical: extend the state to include the remaining capacity of every bin, not just one.

For two bins the state is (item index, remaining capacity of bin 1, remaining capacity of bin 2); each item is either skipped, placed in bin 1 (if it fits), or placed in bin 2 (if it fits). A third bin adds one more capacity dimension to the state — the recursion is identical, only the branching factor and state size grow. Beyond two or three bins and small capacities, this state space explodes, and production systems fall back to greedy-plus-local-search heuristics or an ILP solver instead of exact DP.

from functools import lru_cache

def multiple_knapsack(weights, values, cap1, cap2):
    """
    Multiple Knapsack, 2 bins: assign each item to at most one bin.
    State: (item index, remaining capacity of bin 1, remaining capacity of bin 2)
    Exact and exponential-ish in the number of bins -- fine for 2-3 small bins,
    not a general solution (the problem is NP-hard for many bins).
    """
    n = len(weights)

    @lru_cache(maxsize=None)
    def best(i, r1, r2):
        if i == n:
            return 0
        result = best(i + 1, r1, r2)                       # skip item i
        if weights[i] <= r1:
            result = max(result, values[i] + best(i + 1, r1 - weights[i], r2))
        if weights[i] <= r2:
            result = max(result, values[i] + best(i + 1, r1, r2 - weights[i]))
        return result

    answer = best(0, cap1, cap2)
    best.cache_clear()
    return answer

# Example: 5 items, 2 trucks with capacities 10 and 8
weights = [4, 8, 5, 3, 7]
values = [10, 18, 12, 7, 15]
print(f"Multiple Knapsack (2 bins): {multiple_knapsack(weights, values, 10, 8)}")  # 40

// Multiple Knapsack, 2 bins -- state (item, remaining cap 1, remaining cap 2)
#include <vector>
#include <algorithm>
#include <iostream>

class MultipleKnapsack {
public:
    static int solve(const std::vector<int>& weights, const std::vector<int>& values,
                      int cap1, int cap2) {
        int n = static_cast<int>(weights.size());
        std::vector<std::vector<std::vector<int>>> memo(
            n + 1, std::vector<std::vector<int>>(cap1 + 1, std::vector<int>(cap2 + 1, -1)));
        return rec(weights, values, 0, cap1, cap2, memo);
    }

private:
    static int rec(const std::vector<int>& weights, const std::vector<int>& values,
                    int i, int r1, int r2,
                    std::vector<std::vector<std::vector<int>>>& memo) {
        if (i == static_cast<int>(weights.size())) return 0;
        if (memo[i][r1][r2] != -1) return memo[i][r1][r2];

        int result = rec(weights, values, i + 1, r1, r2, memo);
        if (weights[i] <= r1)
            result = std::max(result, values[i] + rec(weights, values, i + 1, r1 - weights[i], r2, memo));
        if (weights[i] <= r2)
            result = std::max(result, values[i] + rec(weights, values, i + 1, r1, r2 - weights[i], memo));

        return memo[i][r1][r2] = result;
    }
};

int main() {
    std::vector<int> weights{4, 8, 5, 3, 7};
    std::vector<int> values{10, 18, 12, 7, 15};
    std::cout << "Multiple Knapsack (2 bins): " << MultipleKnapsack::solve(weights, values, 10, 8) << '\n'; // 40
}

// Multiple Knapsack, 2 bins -- state (item, remaining cap 1, remaining cap 2)
public class MultipleKnapsack {
    static int[][][] memo;
    static int[] weights, values;

    static int solve(int[] w, int[] v, int cap1, int cap2) {
        weights = w;
        values = v;
        memo = new int[w.length + 1][cap1 + 1][cap2 + 1];
        for (int[][] a : memo) for (int[] b : a) java.util.Arrays.fill(b, -1);
        return rec(0, cap1, cap2);
    }

    static int rec(int i, int r1, int r2) {
        if (i == weights.length) return 0;
        if (memo[i][r1][r2] != -1) return memo[i][r1][r2];

        int result = rec(i + 1, r1, r2);
        if (weights[i] <= r1)
            result = Math.max(result, values[i] + rec(i + 1, r1 - weights[i], r2));
        if (weights[i] <= r2)
            result = Math.max(result, values[i] + rec(i + 1, r1, r2 - weights[i]));

        return memo[i][r1][r2] = result;
    }

    public static void main(String[] args) {
        int[] weights = {4, 8, 5, 3, 7};
        int[] values = {10, 18, 12, 7, 15};
        System.out.println("Multiple Knapsack (2 bins): " + solve(weights, values, 10, 8)); // 40
    }
}

4. Subset Sum

Core insight: Subset Sum asks a yes/no question — can some subset of the items sum to exactly $s$? State: $dp[i][s]$ = true if the first $i$ items can sum to exactly $s$. Transition: $dp[i][s] = dp[i-1][s] \lor (\text{nums}[i-1] \le s \land dp[i-1][s-\text{nums}[i-1]])$, meaning either the $i$-th item is skipped, or it is used and the remaining $i-1$ items must reach $s - \text{nums}[i-1]$. Base case: $dp[0][0]$ = true, and $dp[0][s]$ = false for every $s > 0$. 
def subset_sum(nums, target):
    """
    Subset Sum: can some subset of nums sum to exactly target?
    dp[i][s] = can the first i items sum to exactly s
    Time: O(n * target), Space: O(n * target)
    """
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = True

    for i in range(1, n + 1):
        for s in range(target + 1):
            dp[i][s] = dp[i - 1][s]
            if not dp[i][s] and nums[i - 1] <= s:
                dp[i][s] = dp[i - 1][s - nums[i - 1]]

    return dp[n][target]

# Example
nums = [3, 34, 4, 12, 5, 2]
target = 9
print(f"Subset Sum: {subset_sum(nums, target)}")  # True (4 + 5, or 3 + 4 + 2)

// Subset Sum
#include <vector>
#include <iostream>

bool subsetSum(const std::vector<int>& nums, int target) {
    int n = static_cast<int>(nums.size());
    std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(target + 1, false));
    dp[0][0] = true;

    for (int i = 1; i <= n; i++) {
        for (int s = 0; s <= target; s++) {
            dp[i][s] = dp[i - 1][s];
            if (!dp[i][s] && nums[i - 1] <= s) {
                dp[i][s] = dp[i - 1][s - nums[i - 1]];
            }
        }
    }
    return dp[n][target];
}

int main() {
    std::vector<int> nums{3, 34, 4, 12, 5, 2};
    int target = 9;
    std::cout << "Subset Sum: " << (subsetSum(nums, target) ? "true" : "false") << '\n'; // true
}

// Subset Sum
public class SubsetSum {
    static boolean subsetSum(int[] nums, int target) {
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][target + 1];
        dp[0][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int s = 0; s <= target; s++) {
                dp[i][s] = dp[i - 1][s];
                if (!dp[i][s] && nums[i - 1] <= s) {
                    dp[i][s] = dp[i - 1][s - nums[i - 1]];
                }
            }
        }
        return dp[n][target];
    }

    public static void main(String[] args) {
        int[] nums = {3, 34, 4, 12, 5, 2};
        int target = 9;
        System.out.println("Subset Sum: " + subsetSum(nums, target)); // true
    }
}
Worked Example

Trace subset_sum([6, 2, 5], 7)

Track the set of sums reachable after each item is considered, instead of a full boolean grid:

Items processedReachable sums
none{0}
6{0, 6}
6, 2{0, 2, 6, 8}
6, 2, 5{0, 2, 5, 6, 7, 8, 11, 13}

Target 7 appears once all three items are considered — reached by $2 + 5$ — so subset_sum([6, 2, 5], 7) is true. Each row is exactly one pass of the $dp[i][\cdot]$ recurrence: every new item either leaves a sum unreached, or adds (sum + item) to the reachable set.

Partition Equal Subset Sum

Partition Equal Subset Sum asks whether an array can be split into two subsets with equal totals — which is exactly Subset Sum with target = total_sum // 2 (and an immediate "no" if the total is odd).

def can_partition(nums):
    """
    LeetCode 416: Partition Equal Subset Sum
    Reduces directly to Subset Sum with target = total_sum // 2.
    """
    total = sum(nums)
    if total % 2 != 0:
        return False

    target = total // 2
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = True
    for i in range(1, n + 1):
        for s in range(target + 1):
            dp[i][s] = dp[i - 1][s]
            if not dp[i][s] and nums[i - 1] <= s:
                dp[i][s] = dp[i - 1][s - nums[i - 1]]
    return dp[n][target]

# Examples
print(f"can_partition([1, 5, 11, 5]): {can_partition([1, 5, 11, 5])}")  # True  (11 == 1+5+5)
print(f"can_partition([1, 2, 3, 5]): {can_partition([1, 2, 3, 5])}")    # False

// Partition Equal Subset Sum -- reduces to Subset Sum with target = total / 2
#include <vector>
#include <numeric>
#include <iostream>

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;
    int n = static_cast<int>(nums.size());
    std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(target + 1, false));
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        for (int s = 0; s <= target; s++) {
            dp[i][s] = dp[i - 1][s];
            if (!dp[i][s] && nums[i - 1] <= s) {
                dp[i][s] = dp[i - 1][s - nums[i - 1]];
            }
        }
    }
    return dp[n][target];
}

int main() {
    std::vector<int> a{1, 5, 11, 5};
    std::vector<int> b{1, 2, 3, 5};
    std::cout << "can_partition([1,5,11,5]): " << (canPartition(a) ? "true" : "false") << '\n'; // true
    std::cout << "can_partition([1,2,3,5]): " << (canPartition(b) ? "true" : "false") << '\n'; // false
}

// Partition Equal Subset Sum -- reduces to Subset Sum with target = total / 2
import java.util.Arrays;

public class PartitionEqualSubsetSum {
    static boolean canPartition(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total % 2 != 0) return false;

        int target = total / 2;
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][target + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int s = 0; s <= target; s++) {
                dp[i][s] = dp[i - 1][s];
                if (!dp[i][s] && nums[i - 1] <= s) {
                    dp[i][s] = dp[i - 1][s - nums[i - 1]];
                }
            }
        }
        return dp[n][target];
    }

    public static void main(String[] args) {
        System.out.println("can_partition([1,5,11,5]): " + canPartition(new int[]{1, 5, 11, 5})); // true
        System.out.println("can_partition([1,2,3,5]): " + canPartition(new int[]{1, 2, 3, 5}));   // false
    }
}

5. Ordered Compositions

Core insight: Part 15's coin_change_ways puts coins in the outer loop and amount in the inner loop — each coin type is fully "locked in" before the next is considered, so $1+2$ and $2+1$ collapse into the same combination. Swap the loop order — amount in the outer loop, coins in the inner loop — and every amount is rebuilt from scratch by trying every coin, so $1+2$ and $2+1$ are counted as two different ordered compositions. 
def coin_change_combinations(coins, amount):
    """
    Recap of Part 15's coin_change_ways: coins outer, amount inner.
    Order doesn't matter -- {1, 2} and {2, 1} are the same combination.
    """
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    return dp[amount]

def coin_change_compositions(coins, amount):
    """
    Ordered Compositions: amount outer, coins inner.
    Order matters -- (1, 2) and (2, 1) are counted separately.
    Time: O(amount * len(coins)), Space: O(amount)
    """
    dp = [0] * (amount + 1)
    dp[0] = 1
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] += dp[i - coin]
    return dp[amount]

# Example
coins = [1, 2]
amount = 3
print(f"Combinations (order ignored): {coin_change_combinations(coins, amount)}")  # 2 -> {1,1,1}, {1,2}
print(f"Compositions (order matters): {coin_change_compositions(coins, amount)}")  # 3 -> (1,1,1), (1,2), (2,1)

// Combinations (coin outer) vs Compositions (amount outer)
#include <vector>
#include <iostream>

int coinChangeCombinations(const std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) dp[i] += dp[i - coin];
    }
    return dp[amount];
}

int coinChangeCompositions(const std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

int main() {
    std::vector<int> coins{1, 2};
    int amount = 3;
    std::cout << "Combinations: " << coinChangeCombinations(coins, amount) << '\n'; // 2
    std::cout << "Compositions: " << coinChangeCompositions(coins, amount) << '\n'; // 3
}

// Combinations (coin outer) vs Compositions (amount outer)
public class OrderedCompositions {
    static int coinChangeCombinations(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) dp[i] += dp[i - coin];
        }
        return dp[amount];
    }

    static int coinChangeCompositions(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2};
        int amount = 3;
        System.out.println("Combinations: " + coinChangeCombinations(coins, amount)); // 2
        System.out.println("Compositions: " + coinChangeCompositions(coins, amount)); // 3
    }
}
Loop orderStepdp array after step
Combinations (coin outer)start[1, 0, 0, 0]
process coin 1[1, 1, 1, 1]
process coin 2[1, 1, 2, 2]
Compositions (amount outer)dp[0][1, 0, 0, 0]
dp[1] (coins 1, 2)[1, 1, 0, 0]
dp[2] (coins 1, 2)[1, 1, 2, 0]
dp[3] (coins 1, 2)[1, 1, 2, 3]

In the combinations pass, coin 1 finishes populating dp[1..3] before coin 2 is ever considered, so a coin-2-then-coin-1 arrangement is never separately counted. In the compositions pass, dp[3] is built by asking "what was the count for $3-1=2$?" and "what was the count for $3-2=1$?" independently, at a point where both already include every arrangement that used any mix of coins — so $(1,2)$ and $(2,1)$ both get added in.

Bounded Coins

Bounded Coins is Coin Change with a limited supply per denomination — denomination $i$ can be used at most counts[i] times when making the amount. This is the same shape of problem as Bounded Knapsack, so the same binary-grouping trick applies directly: split each denomination's supply into $O(\log \text{counts}[i])$ super-coins, then run a 0/1-style minimum-coins DP over all super-coins, tracking the number of physical coins each super-coin represents as its cost.

def bounded_min_coins(coins, counts, amount):
    """
    Bounded Coins: coins[i] may be used at most counts[i] times.
    Reuses the Bounded Knapsack binary-grouping trick: each super-coin of
    block size k contributes weight k*coin (toward amount) and cost k
    (physical coins spent).
    Time: O(len(coins) * amount * log(max(counts))), Space: O(amount)
    """
    INF = float('inf')
    super_weight = []
    super_cost = []
    for coin, c in zip(coins, counts):
        k = 1
        remaining = c
        while remaining > 0:
            take = min(k, remaining)
            super_weight.append(coin * take)
            super_cost.append(take)
            remaining -= take
            k *= 2

    dp = [INF] * (amount + 1)
    dp[0] = 0
    for w, cost in zip(super_weight, super_cost):
        for s in range(amount, w - 1, -1):
            if dp[s - w] != INF:
                dp[s] = min(dp[s], dp[s - w] + cost)
    return dp[amount] if dp[amount] != INF else -1

# Example: 5 ones, 2 twos, 1 five, make amount 12
coins = [1, 2, 5]
counts = [5, 2, 1]
amount = 12
print(f"Bounded Coins (min coins): {bounded_min_coins(coins, counts, amount)}")  # 6 -> 5+2+2+1+1+1

// Bounded Coins via binary grouping (reuses the Bounded Knapsack trick)
#include <vector>
#include <algorithm>
#include <limits>
#include <iostream>

int boundedMinCoins(const std::vector<int>& coins, const std::vector<int>& counts, int amount) {
    const int INF = std::numeric_limits<int>::max() / 2;
    std::vector<int> superWeight;
    std::vector<int> superCost;

    for (std::size_t i = 0; i < coins.size(); ++i) {
        int k = 1;
        int remaining = counts[i];
        while (remaining > 0) {
            int take = std::min(k, remaining);
            superWeight.push_back(coins[i] * take);
            superCost.push_back(take);
            remaining -= take;
            k *= 2;
        }
    }

    std::vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (std::size_t s = 0; s < superWeight.size(); ++s) {
        int w = superWeight[s];
        int cost = superCost[s];
        for (int a = amount; a >= w; --a) {
            if (dp[a - w] != INF) dp[a] = std::min(dp[a], dp[a - w] + cost);
        }
    }
    return dp[amount] >= INF ? -1 : dp[amount];
}

int main() {
    std::vector<int> coins{1, 2, 5};
    std::vector<int> counts{5, 2, 1};
    int amount = 12;
    std::cout << "Bounded Coins (min coins): " << boundedMinCoins(coins, counts, amount) << '\n'; // 6
}

// Bounded Coins via binary grouping (reuses the Bounded Knapsack trick)
import java.util.*;

public class BoundedCoins {
    static int boundedMinCoins(int[] coins, int[] counts, int amount) {
        final int INF = Integer.MAX_VALUE / 2;
        List<Integer> superWeight = new ArrayList<>();
        List<Integer> superCost = new ArrayList<>();

        for (int i = 0; i < coins.length; i++) {
            int k = 1;
            int remaining = counts[i];
            while (remaining > 0) {
                int take = Math.min(k, remaining);
                superWeight.add(coins[i] * take);
                superCost.add(take);
                remaining -= take;
                k *= 2;
            }
        }

        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int s = 0; s < superWeight.size(); s++) {
            int w = superWeight.get(s);
            int cost = superCost.get(s);
            for (int a = amount; a >= w; a--) {
                if (dp[a - w] != INF) dp[a] = Math.min(dp[a], dp[a - w] + cost);
            }
        }
        return dp[amount] >= INF ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int[] counts = {5, 2, 1};
        int amount = 12;
        System.out.println("Bounded Coins (min coins): " + boundedMinCoins(coins, counts, amount)); // 6
    }
}

6. A Note on Bitset Optimization

A faster Subset Sum, not shown here: Subset Sum's "reachable sums" can be packed into a single bitset (one bit per possible sum) instead of a boolean array. Adding an item becomes one operation, reachable |= reachable << weight, which updates every reachable sum in parallel — a machine word processes dozens or hundreds of sums per shift-and-OR instead of one sum per loop iteration. This is a genuine asymptotic win in practice (a constant-factor speedup equal to the machine word size), not just a micro-optimization. The general technique, bitset DP, extends well beyond Subset Sum to other DPs whose transitions are unions or shifts over a bounded domain. It is covered in full, with implementation and complexity analysis, in the sibling lesson Bitset DP. Nothing here depends on it; it is worth knowing it exists before you reach for a plain boolean array on a large target.

7. Complexity Comparison Table

VariantState DefinitionTimeSpace
Bounded Knapsack$dp[w]$ over binary-grouped super-items$O(n \cdot W \cdot \log(\max c_i))$$O(W)$
Multiple Knapsack (small, fixed bins)$dp[i][r_1][r_2]\dots$, remaining capacity per bin$O(n \cdot \prod_b (\text{cap}_b + 1))$same as time (memo table)
Subset Sum$dp[i][s]$ = first $i$ items reach sum $s$$O(n \cdot \text{target})$$O(n \cdot \text{target})$, or $O(\text{target})$ 1D
Partition Equal Subset SumSubset Sum with target $= \text{sum}/2$$O(n \cdot \text{sum})$$O(\text{sum})$
Ordered Compositions$dp[a]$, amount in the outer loop$O(\text{amount} \cdot |\text{coins}|)$$O(\text{amount})$
Bounded Coins$dp[s]$ over binary-grouped super-coins$O(|\text{coins}| \cdot \text{amount} \cdot \log(\max \text{counts}))$$O(\text{amount})$

8. Applications and Alternatives

Where each variant shows up in practice

  • Bounded Knapsack: cargo or cart selection with limited per-SKU inventory, where items are not one-off and not infinite.
  • Multiple Knapsack: loading a small, fixed fleet of trucks or a handful of shipping containers; beyond a few bins, exact DP gives way to heuristics or ILP solvers.
  • Subset Sum: checking exact-change feasibility, matching tax lots or invoice line items to a target total, and the historical (now broken) knapsack-based public-key cryptosystems.
  • Partition Equal Subset Sum: splitting a workload or a set of tasks between two workers as evenly as possible.
  • Ordered Compositions: counting the number of distinct move sequences (e.g. weighted staircase steps) that reach a target, where sequencing itself is part of the answer.
  • Bounded Coins: vending machines and cash registers with a finite till, where minimum change must respect actual coin stock.

All six are DP at heart, but the alternative worth knowing is when DP itself is the wrong tool: for Subset Sum and Partition with very large sums but few items, a meet-in-the-middle split (enumerate half the items, sort, binary search the other half) can beat $O(n \cdot \text{sum})$ when sum dominates $2^{n/2}$. For Multiple Knapsack at real fleet scale, a mixed-integer program or a metaheuristic replaces exact DP entirely.

9. Exercises and Mastery

Easy

  1. Trace subset_sum([1, 5, 11, 5], 10) using the reachable-sums table from Section 4, and confirm the answer is true.
  2. State why subset_sum(nums, 0) is always true regardless of nums.

Medium

  1. Partition to K Equal Sum Subsets generalizes Partition Equal Subset Sum from 2 buckets to $k$ buckets, each required to sum to $\text{total}/k$. Design (code optional) an approach: a bitmask DP over which items have been used ($dp[\text{mask}]$ = remainder in the bucket currently being filled) is one option; backtracking with pruning (sort descending, skip duplicate bucket-fill attempts) is another. Explain why the plain Subset Sum reduction that works for $k=2$ does not extend cleanly to $k=3$ or more.
  2. Explain why Ordered Compositions' state, $dp[a]$, does not need to track which coins were already used, while a naive "count distinct sequences" approach might tempt you to track a used-set.

Hard

  1. For items with weights $[5, 7, 3]$, values $[10, 14, 7]$, and counts $[100, 50, 200]$, work out how many super-items binary grouping produces for each (the grouping loop from Section 3 gives 7, 6, and 8 super-items respectively), then explain why solving 0/1 Knapsack on 21 super-items is dramatically cheaper than the naive $O(n \cdot W \cdot \max c_i)$ approach when $W$ is in the thousands.
  2. Prove that binary grouping's take = min(k, remaining) loop always makes every count from $0$ to $c_i$ reachable as a subset sum of the produced groups, even when the last group is smaller than the doubling sequence would predict.
Mastery challenge: A warehouse has several outbound trucks, each with its own capacity, and a limited stock of each product SKU. Design an approach that first applies binary grouping per SKU (Bounded Knapsack), then feeds the resulting super-items into a small-bin Multiple Knapsack DP. State the combined complexity, identify the point at which the truck count makes exact DP impractical, and name the fallback strategy you would reach for at that point.

Review rhythm: tomorrow, reconstruct the binary-grouping loop and the combinations/compositions loop-order swap from memory. Next week, implement all six variants in a language you did not use here. Several weeks later, recognize a "limited supply" or "order matters" constraint in a new problem and immediately name which of these six patterns applies, without searching for it.

10. Summary Cheat Sheet

  • Bounded Knapsack: binary-group each item into $O(\log c_i)$ super-items, then run ordinary 0/1 Knapsack.
  • Multiple Knapsack: extend the DP state with one remaining-capacity dimension per bin; exact only for a small, fixed number of bins.
  • Subset Sum: $dp[i][s]$ tracks reachability, not value — a yes/no DP, not a max/min DP.
  • Partition Equal Subset Sum: Subset Sum with target $= \text{sum}/2$; nothing new to derive.
  • Ordered Compositions: swapping the coin/amount loop order turns "ways" (Part 15) into "ordered ways" — no new state, just a different iteration order.
  • Bounded Coins: the same binary-grouping trick as Bounded Knapsack, applied to a minimum-coins objective instead of a maximum-value objective.
  • Binary grouping preserves optimization answers (min/max) exactly, but it is not safe to reuse for counting the number of ways — it can create multiple representations of the same physical count.
  • Bitset DP accelerates Subset Sum's inner loop by packing reachable sums into machine words; see Bitset DP for the full technique.

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Browse the complete 18-level algorithm curriculum and practical project sequence.

Open the DSA Hub
Part 15: Core DP Patterns

The 0/1 Knapsack, Unbounded Knapsack, and both Coin Change variants (minimum coins, number of ways) this lesson builds directly on top of.

Read Part 15
Bitset DP

Pack reachable-state DPs into machine words for a constant-factor speedup, starting from the Subset Sum bitset idea introduced above.

Read Bitset DP