Why this matters when you build with AI
Ask an AI tool for a bounded knapsack solution and the first program it writes is usually the simplest one: it copies each item once per available copy and runs the 0/1 knapsack loop over every copy. That program is correct and passes the samples. It fails when the counts are large. If one kind has 10^6 copies, the program does a million passes over the table, and a judge or a production job runs out of time.
The fix is to count the work before you run anything. Write the number of copies, the number of table cells, and the steps per cell, then multiply. Only then pick the method. This lesson gives three ways to solve the same bounded problem, measures how many steps each one runs, and shows the bugs that AI tools produce in each one.
A prompt that asks for the count in the answer, so a wrong method shows up early:
Write C++17 code for this problem. The first line has n and W. Each of the next n lines has
p w c: a price, a weight and the number of copies available. Choose at most c copies of each kind
so that the total weight is at most W and the total price is largest. Use long long.
Before the code, say how many inner-loop steps the program runs in the worst case, written as a
formula in n, W and the sum of the counts. Then give the output for the sample "3 10", "6 3 2",
"10 4 1", "4 2 5". The output is 22.A good answer gives a formula that depends on the counts. A bad answer says the program is O(n W) and never mentions the copies, which hides the cost of the naive method. Check the formula against the measurements in this lesson.
Terms used
- A knapsack problem chooses items with a weight limit W and tries to get the largest total value.
- A kind is a group of identical items with the same price and weight. A copy is one item of that kind.
- 0/1 knapsack means each item is taken once or not at all.
- Unbounded knapsack means each kind can be taken any number of times.
- Bounded knapsack means each kind has a count c, and at most c copies may be taken.
- An at-most table is the table
dp[x]that holds the best value with total weight at most x. It starts with all zeros, so no cell is ever unreachable. - Binary splitting writes a count as a set of pieces, where each piece is one 0/1 item that stands for several copies.
- A residue class is the set of numbers with the same remainder when divided by w. For w = 3 the classes are 0, 3, 6, ... and 1, 4, 7, ... and 2, 5, 8, ...
- A monotone queue is a deque (a list you can add and remove at both ends) that keeps candidates in an order so the best one is always at the front.
- A bitset is an array of bits where one shift moves all the bits together. It works on 64 bits per machine word.
The idea: one kind at a time, with an at-most table
Here is the problem used in the whole lesson. A stall can carry W grams. There are n kinds of sweets. Kind i has price p_i, weight w_i and count c_i, which is how many pieces the stall has. Choose how many pieces of each kind to take, so that the total weight is at most W and the total price is as large as possible.
Start with the smallest case, one kind with one copy, which is the 0/1 knapsack. Let dp[x] be the best price with total weight at most x. Taking one copy of a kind with weight w and price p gives this update:
dp[x] = max(dp[x], dp[x - w] + p)Run x from W down to w. The order matters, so here is a tiny example with one item of price 5 and weight 2, and W = 4. Going downward, dp[4] reads dp[2] while dp[2] still holds the old value 0, so dp[4] becomes 5. Then dp[2] becomes 5. The final table is 0, 0, 5, 5, 5, and the answer for weight 4 is 5, which is right.
Going upward would change dp[2] to 5 first, and then dp[4] would read that new value and add the item a second time. The answer would be 10, which uses the same item twice. The program does not crash and prints a number that looks plausible. Section "Common mistakes" shows this exact output.
The unbounded knapsack is the same update with the loop run upward, so a copy can be reused. On the tiny example the unbounded answer is 10, because two copies fit in weight 4. Keep the two loop directions apart in your head. Downward is for 0/1 and bounded items, upward is for unlimited items.
For the bounded problem, the naive idea is to make each copy its own 0/1 item. That is method A.
Method A: expand every copy
The program reads each kind, then runs the 0/1 loop once for each copy.
// Stall stock, method A: expand every copy into its own 0/1 item.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
// dp[x] = best price with total weight <= x. All zero at the start.
vector<long long> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
long long p;
int w, c;
cin >> p >> w >> c;
for (int copy = 0; copy < c; copy++) {
// One copy is one 0/1 item. Go downwards so one copy is used at most once.
for (int x = W; x >= w; x--)
dp[x] = max(dp[x], dp[x - w] + p);
}
}
cout << dp[W] << "\n";
return 0;
}The sample input is 3 10 on the first line, then 6 3 2, 10 4 1 and 4 2 5. Its output is 22. Compile and run it with g++ -O2 -std=c++17. The answer 22 comes from one piece of kind 2 (price 10, weight 4) and three pieces of kind 3 (price 4, weight 2 each), which together weigh 10 and are worth 22.
The cost is about (sum of the counts) times W. For the sample that is 8 copies times 10, so about 80 steps. For a kind with c = 10^6 copies and W = 10^5, the program runs about 10^11 steps for that kind alone, far beyond a usual contest time limit. Method A is correct, so it is a good reference to test against, and a poor final program when the counts are large.
Method B: binary splitting
Binary splitting replaces c copies with a few pieces. The pieces have sizes 1, 2, 4, 8, and so on, and the last piece takes whatever is left. Each piece is one 0/1 item that stands for that many copies.
Why does this work? Take c = 5. The pieces are 1, 2 and 2. Every count from 0 to 5 is a sum of some of these pieces: 0 is no piece, 1 is the first piece, 2 is the second piece, 3 is 1 plus 2, 4 is 2 plus 2, 5 is 1 plus 2 plus 2. So the 0/1 loop over the three pieces can pick any number of copies from 0 to 5, and no more.
The rule to get the pieces is: take 1, then 2, then 4, and so on, but never take more than what is left. Here is what the rule gives for a few counts:
c = 1 pieces 1
c = 2 pieces 1, 1
c = 5 pieces 1, 2, 2
c = 13 pieces 1, 2, 4, 6
c = 100 pieces 1, 2, 4, 8, 16, 32, 37A common mistake is to use the powers 1, 2, 4 for c = 5 and skip the remainder. The pieces 1, 2, 4 add up to 7, so the program can take 6 or 7 copies. Section "Common mistakes" shows the real output of that mistake.
The number of pieces is about the logarithm (base 2) of c, so it is at most about 30 for counts up to 10^9.
// Stall stock, method B: binary splitting of each count, then 0/1 knapsack.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<long long> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
long long p;
int w, c;
cin >> p >> w >> c;
int left = c;
// Pieces of size 1, 2, 4, ... and then the remainder.
for (int piece = 1; left > 0; piece *= 2) {
int take = min(piece, left);
left -= take;
long long tw = (long long)take * w;
long long tp = (long long)take * p;
if (tw > W) continue;
// Each piece is one 0/1 item of weight tw and price tp.
for (long long x = W; x >= tw; x--)
dp[x] = max(dp[x], dp[x - tw] + tp);
}
}
cout << dp[W] << "\n";
return 0;
}On the sample it prints 22. The sample has 6 pieces in total (kind 1 has two pieces, kind 2 has one, kind 3 has three), so the loop runs 6 times over the table instead of 8.
Why are the pieces enough? If m is a count from 0 to c, write m as the sum of the pieces you use. The pieces 1, 2, ..., 2^(k-1) can make every number from 0 to 2^k - 1. The last piece is at most 2^k, so it can cover the rest. I checked with a short script that for every count from 1 to 1000, the pieces make every total from 0 to c and nothing above c.
Method C: a monotone queue per residue class
Method B is fast enough for most contests. Method C removes the log factor completely, and it is the idea behind the name of this section.
Take one kind with weight w, price p and count c. Look at the capacities x that have the same remainder r when divided by w. They form a chain: r, r + w, r + 2w, and so on. Index the chain by s, so the capacity is r + s * w. Taking t copies of this kind moves the best answer from chain index s to chain index t, where s is between t - c and t, and the gain is (t - s) * p.
So the new value at index t is
new[t] = max over s in [t - c, t] of (dp[s] + (t - s) * p)Rewrite the right side as t * p + (dp[s] - s * p). The term dp[s] - s * p depends only on s, and the window of allowed s slides by one step each time t goes up by one. A sliding window maximum over a fixed-width window is the classic use of a monotone queue. The queue stores indexes s with decreasing keys dp[s] - s * p. The front is always the best index in the window. When t grows, add t at the back and remove the old indexes from the front.
Here is a worked trace on one chain. Let w = 2, p = 3 and c = 2. The previous table gives these values on the chain: index 0 holds 0, index 1 holds 2, index 2 holds 5 and index 3 holds 6. The keys dp[s] - 3s are 0, -1, -1 and -3.
t = 0 window [0] keys 0 new = 0 + 0 = 0
t = 1 window [0, 1] keys 0, -1 new = 3 + 0 = 3
t = 2 window [0, 1, 2] keys 0, -1, -1 new = 6 + 0 = 6
t = 3 window [1, 2, 3] keys -1, -1, -3 new = 9 + (-1) = 8Check t = 3 by hand. Taking 0, 1 or 2 copies from index 3 gives 6, 5 + 3 = 8 and 2 + 6 = 8. The maximum is 8, which matches the trace. The window moved from [0, 2] to [1, 3] because index 0 is now more than c steps back.
// Stall stock, method C: a monotone queue per residue class modulo w, O(n * W) in total.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<long long> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
long long p;
int w, c;
cin >> p >> w >> c;
vector<long long> nd(W + 1, 0);
// Positions x with the same x mod w form a chain: r, r + w, r + 2w, ...
for (int r = 0; r < w && r <= W; r++) {
int T = (W - r) / w; // last index on this chain
// key(s) = dp[r + s*w] - s*p. Then nd[r + t*w] = t*p + max over s in [t-c, t] of key(s).
auto key = [&](int s) {
return dp[r + (long long)s * w] - (long long)s * p;
};
deque<int> dq; // indexes s whose keys decrease from front to back
for (int t = 0; t <= T; t++) {
long long kt = key(t);
while (!dq.empty() && key(dq.back()) <= kt) dq.pop_back();
dq.push_back(t);
while (dq.front() < t - c) dq.pop_front(); // leave the window [t-c, t]
nd[r + (long long)t * w] = (long long)t * p + key(dq.front());
}
}
dp = nd;
}
cout << dp[W] << "\n";
return 0;
}The program reads the old row dp and writes the new row nd, so every window sees the values from before this kind. Writing into the same array while reading it would mix two kinds together and give wrong answers.
Each kind costs one pass over all W + 1 cells, so the total is n * W, and the count c does not change the cost. This is why method C wins when the counts are huge. It needs two rows of W + 1 numbers, one old and one new, which is about 1.6 MB for W = 10^5 with 8-byte numbers.
Method D: bitset for yes or no questions
Sometimes you do not need the best value, only whether a total weight can be reached. The question "which weights from 0 to W can the stall fill exactly?" is a subset-sum question. A bitset answers it fast. Bit x is 1 when weight x is reachable. Taking a piece of weight tw means shifting the whole bitset by tw and combining it with the old bitset with OR. Each machine word holds 64 bits, so one shift and OR touches 64 positions per word operation.
// Feasibility only: how many total weights in 0..W can be made with at most c copies of each kind.
#include <bits/stdc++.h>
using namespace std;
const int MAXW = 100000;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
bitset<MAXW + 1> reach;
reach[0] = 1;
for (int i = 0; i < n; i++) {
long long p;
int w, c;
cin >> p >> w >> c;
int left = c;
for (int piece = 1; left > 0; piece *= 2) {
int take = min(piece, left);
left -= take;
long long sh = (long long)take * w;
if (sh <= W) reach |= reach << sh; // shifting only moves bits up, so bits above W never affect bits <= W
}
}
int cnt = 0;
for (int x = 0; x <= W; x++)
if (reach[x]) cnt++;
cout << cnt << "\n";
return 0;
}On the sample it prints 10. Weight 1 is the only value from 0 to 10 that the stall cannot fill exactly, because the weights are 2, 3 and 4 and no combination makes 1. The bitset does not track prices, so it cannot give the maximum price. Use it for yes or no questions only, such as "can we pay exactly this amount?".
Comparing the methods on the same input
I generated three large inputs with a seeded random generator. Each kind has a price from 1 to 1000, a weight from 1 to 300 and a count from 1 to 100. The table gives the number of inner-loop steps, which I counted with a script from the counts, and one wall-clock run of each program on this machine.
input kinds W total copies pieces naive steps split steps mono steps (n * W)
big_a 100 20000 4895 579 97,900,000 11,580,000 2,000,000
big_b 1000 20000 50721 5825 1,014,420,000 116,500,000 20,000,000
big_c 100 100000 5199 579 519,900,000 57,900,000 10,000,000The step counts are the exact numbers of table updates the methods perform, with the naive count taken as copies times W. The actual inner loop of method A skips positions below w, so its real count is a little lower.
input naive A split B mono C answer
big_a 0.24 s 0.15 s 0.13 s 356301
big_b 1.18 s 0.14 s 0.35 s 1457525
big_c 0.55 s 0.25 s 0.23 s 1188675These times come from one run on one machine. Another run gave 0.11 s for method A on big_a and 0.62 s on big_b, so the variation between runs is large. Your times will differ, so use them for the shape only: method A grows with the total number of copies, and methods B and C grow much more slowly. All three methods gave the same answer on each of the three inputs, and on 400 random small inputs against a brute force program.
The brute force program tries every count vector. It is in Python, so it is only useful on tiny inputs:
import sys
from itertools import product
data = sys.stdin.read().split()
n, W = int(data[0]), int(data[1])
kinds = []
idx = 2
for _ in range(n):
p, w, c = int(data[idx]), int(data[idx + 1]), int(data[idx + 2])
kinds.append((p, w, c))
idx += 3
best = 0
for ks in product(*[range(c + 1) for (_, _, c) in kinds]):
weight = sum(k * w for k, (_, w, _) in zip(ks, kinds))
if weight <= W:
best = max(best, sum(k * p for k, (p, _, _) in zip(ks, kinds)))
print(best)Hands-on exercise
Work on your own machine with a folder that has all four programs.
- Write the three programs (methods A, B and C) from the code in this lesson, and save them as
a.cpp,b.cppandc.cpp. Compile each withg++ -O2 -std=c++17. - Create the sample file with exactly these lines, then run each program on it. Each should print 22.
3 10
6 3 2
10 4 1
4 2 5- Write a generator that prints a random input with n between 1 and 4, W between 0 and 20, prices from 1 to 30, weights from 1 to 8 and counts from 0 to 5. Run 200 seeds through the brute force program and all three methods, and check that all four agree.
- Change the generator so that the count is 10^6 and W is 10^5. Time method A with a timeout of 20 seconds. Then time method C. Record which one finishes.
Show the answer
Answer for step 2: the three programs print 22, and so does the brute force. If one of them prints a different number, check the loop direction first, then the pieces, then the trim of the deque.
Practice problems
- Count the pieces. Write the binary split pieces for c = 37 and say how many there are.
Show the answer
Answer: 1, 2, 4, 8, 16 and 6, which is 6 pieces. The first five pieces add up to 31, and the remainder is 6. The pieces add up to 37 exactly. Use the rule from method B: take 1, then 2, then 4, and so on, and never take more than what is left.
- Choose the method. A problem has n = 500 kinds, each with up to 10^9 copies, and W = 10^5. Which of the four methods can run in time, and why? Give the step count for each method you consider.
Show the answer
Answer: method C, with about n * W = 5 * 10^7 steps. Method B takes about 30 pieces per kind, so 500 * 30 * 10^5 = 1.5 * 10^9 steps, which is slow but may pass a loose limit. Method A needs the total copies, up to 5 * 10^11 times W, so it is not an option. Method D only answers yes or no and cannot give the maximum price.
- Reachable weights. For the sample with W = 6 (the first line becomes
3 6and the kinds stay the same), how many total weights from 0 to 6 can be reached? Use method D to check, and say which weights are missing.
Show the answer
Answer: 6. The weights are 2, 3 and 4, so reachable totals are 0, 2, 3, 4, 5 and 6. Weight 1 is the only one missing. The bitset program prints 6 on this input. Method C prints 14 on the same input as a price, which is a different question.
- Find the bug. Someone changes the trim line in method C to
while (dq.front() <= t - c) dq.pop_front();. Predict the output on the input1 2then1 1 2(one kind, price 1, weight 1, count 2, W = 2), where the correct answer is 2.
Show the answer
Answer: the program prints 1. With the new line, index t - c is also removed, so the window holds only c indexes, and the program can take at most c - 1 copies. The real run prints 1 on this input, where the correct program prints 2. On 100 random small inputs, the buggy line gave a wrong answer on 68 of them. The lesson is that a one-character change in the window can change the answer on almost every test that has a count above 1.
Common mistakes
Loop direction in the 0/1 update. The symptom is an answer that is too large, because one item is used twice. On the tiny input 1 4 then 5 2 1 (one kind, price 5, weight 2, one copy, W = 4), the program with the loop run upward prints 10. The correct answer is 5. The real output from my run:
knap_naive on tiny (one item price 5 weight 2 count 1, W 4): 5
bug_forward on tiny (one item price 5 weight 2 count 1, W 4): 10The bug also shows up with more copies. The same forward loop, run on one kind with count 5, weight 1 and price 1 with W = 100, prints 100 where 5 is correct. Each copy is then reused over and over.
Missing remainder piece. Using the powers 1, 2, 4 for c = 5 lets the program take 7 copies. On the input 1 100 then 1 1 5 (one kind, price 1, weight 1, count 5), the correct answer is 5. The buggy binary splitting prints 7:
knap_naive: 5
bug_split (pieces 1, 2, 4 with no remainder): 7Forgetting to remove old indexes from the monotone queue. Without the trim while (dq.front() < t - c), the window grows and the program takes more copies than allowed. On the sample it prints 24 instead of 22. On big_a it prints 1926474 instead of 356301. The fix is one line, but the symptom is a wrong number, not a crash, so always test on the sample and on a brute force check.
Writing the new row into the old row. If method C writes dp in place while it still needs the old values, a window reads a value from this kind, and the same copy can be counted twice. Keep a separate nd array, as the code does.
Using int for totals. Prices can reach 10^9 and counts can reach 10^9, so a single total can pass 2^31 - 1, which is about 2.1 * 10^9. Use long long for prices, sums and the answer.
Trusting a bitset answer for a maximum. The bitset in method D only knows which weights are reachable. It has no price. Using its output as the best price gives a number that has no meaning.
Checklist
- Write the number of copies and the number of table cells before choosing a method.
- Use the downward loop for 0/1 and bounded items, and the upward loop only for unbounded items.
- Use the at-most table, starting from all zeros, when you only need the best value.
- For binary splitting, take min(piece, left) at each step, so the pieces add up to c exactly.
- For the monotone queue, trim the front of the deque at every step, and read the old row while writing the new one.
- Check each method against the sample and against a brute force on small random inputs.
- Use long long for every price, weight product and total.
Summary
For a bounded knapsack, the number of copies decides the method. Expanding every copy is simple and correct but costs the total number of copies times W. Binary splitting cuts the number of 0/1 items to about the logarithm of each count. The monotone queue per residue class costs n times W no matter how large the counts are. The bitset answers only yes or no questions about reachable weights. Measure the steps first, then choose.