The bounded knapsack
Item i weighs weights[i], is worth values[i], and has counts[i]
identical copies. Choose how many copies of each to take (between 0 and its count) so that the total weight is at most
capacity, and return the largest total value.
Examples
| Input | Output | Why |
|---|---|---|
weights = [2,3], values = [3,4], counts = [2,1], capacity = 7 | 10 | Both copies of the first item and the second item: weight 7. |
weights = [1,2,3], values = [10,15,40], counts = [2,1,1], capacity = 6 | 65 | Weights 1 + 2 + 3: values 10 + 15 + 40. |
weights = [4], values = [5], counts = [3], capacity = 9 | 10 | Only two copies fit. |
Constraints
- 1 ≤ n ≤ 100
- 1 ≤ weights[i] ≤ 1000
- 1 ≤ counts[i] ≤ 1000
- 0 ≤ capacity ≤ 10⁴
Hints
Hint 1
Treating every copy as a separate 0/1 item works but costs O(capacity · Σ counts).
Hint 2
Any number from 0 to k is a sum of distinct bundles 1, 2, 4, …, 2ᵖ and a remainder.
Hint 3
Turn each item into those bundles and run the 0/1 knapsack, capacities downwards, over the bundles.
Where people lose marks
- Bundles that overshoot the count (1, 2, 4, 8 for a count of 13 allows 15 copies): the last bundle must be the remainder.
- Looping capacities upwards, which lets a bundle be taken twice.
Dry run on [2,3],[3,4],[2,1],7
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 4best0001020304050607
Start with best = 0 for every capacity.
-
Step 2 / 4best0001323334353637
Bundle of 1 × item 1: weight 2, value 3, as a 0/1 item.
-
Step 3 / 4best0001323364656667
Bundle of 1 × item 1: weight 2, value 3, as a 0/1 item.
-
Step 4 / 4best00013243647576107
Bundle of 1 × item 2: weight 3, value 4, as a 0/1 item. best[7] = 10.
How to think about it
Split each item's copies into bundles of sizes 1, 2, 4, … and a final remainder, so that the bundles add up to the count. Every choice of "take t copies" for 0 ≤ t ≤ count is then a choice of a subset of the bundles, and no subset exceeds the count. Each bundle behaves as one 0/1 item of weight size · w and value size · v, so the 0/1 knapsack over all bundles gives the answer, with about log₂(count) bundles per item instead of count.
Complexity. Time O(capacity · Σ log counts) · Space O(capacity)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def knapsack_bounded(weights, values, counts, capacity):
best = [0] * (capacity + 1)
for w, v, k in zip(weights, values, counts):
size = 1
while k > 0:
take = min(size, k) # bundles 1, 2, 4, ..., remainder
bw, bv = take * w, take * v
for c in range(capacity, bw - 1, -1): # 0/1 update for this bundle
best[c] = max(best[c], bv + best[c - bw])
k -= take
size *= 2
return best[capacity]#include <algorithm>
#include <vector>
long long solve(const std::vector<int>& weights, const std::vector<int>& values, const std::vector<int>& counts, int capacity) {
std::vector<long long> best(capacity + 1, 0);
for (size_t i = 0; i < weights.size(); ++i) {
for (long long k = counts[i], size = 1; k > 0; size *= 2) {
long long take = std::min(size, k), bw = take * weights[i], bv = take * values[i]; // one bundle
for (long long c = capacity; c >= bw; --c) best[c] = std::max(best[c], bv + best[c - bw]);
k -= take;
}
}
return best[capacity];
}class Solution {
public long knapsackBounded(int[] weights, int[] values, int[] counts, int capacity) {
long[] best = new long[capacity + 1];
for (int i = 0; i < weights.length; i++) {
for (long k = counts[i], size = 1; k > 0; size *= 2) {
long take = Math.min(size, k), bw = take * weights[i], bv = take * values[i]; // one bundle
for (long c = capacity; c >= bw; c--) best[(int) c] = Math.max(best[(int) c], bv + best[(int) (c - bw)]);
k -= take;
}
}
return best[capacity];
}
}function knapsackBounded(weights, values, counts, capacity) {
const best = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let k = counts[i], size = 1; k > 0; size *= 2) {
const take = Math.min(size, k), bw = take * weights[i], bv = take * values[i]; // one bundle
for (let c = capacity; c >= bw; c--) best[c] = Math.max(best[c], bv + best[c - bw]);
k -= take;
}
}
return best[capacity];
}fn solve(weights: &[i64], values: &[i64], counts: &[i64], capacity: i64) -> i64 {
let cap = capacity as usize;
let mut best = vec![0i64; cap + 1];
for i in 0..weights.len() {
let (mut k, mut size) = (counts[i], 1i64);
while k > 0 {
let take = size.min(k); // one bundle
let (bw, bv) = ((take * weights[i]) as usize, take * values[i]);
if bw <= cap {
for c in (bw..=cap).rev() {
best[c] = best[c].max(bv + best[c - bw]);
}
}
k -= take;
size *= 2;
}
}
best[cap]
}solve :: [Int] -> [Int] -> [Int] -> Int -> Int
solve weights values counts capacity = last (foldl addBundle (replicate (capacity + 1) 0) bundles)
where
-- every item split into bundles of 1, 2, 4, ... copies and a remainder
split k size | k <= 0 = [] | otherwise = let t = min size k in t : split (k - t) (2 * size)
bundles = [(t * w, t * v) | (w, v, k) <- zip3 weights values counts, t <- split k 1]
addBundle best (bw, bv) = [if c >= bw then max b (bv + best !! (c - bw)) else b | (c, b) <- zip [0 ..] best]Variants to try
- Count the ways to reach an exact weight with limited copies.
- The fewest coins for an amount when each coin has a limited supply.
- Speed it up to O(n · capacity) with a monotone deque per residue class.
Next problems
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Medium15 minCount the palindromic substrings
Count every contiguous substring that reads the same backwards, counting different positions separately. Each successful expansion step is one more.
Open the problem →Write a solution and run it against the real test table.
Keep going
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Medium15 minCount the palindromic substrings
Count every contiguous substring that reads the same backwards, counting different positions separately. Each successful expansion step is one more.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.