Knapsack Problem Generator
A bag with a weight limit, a list of items with weights and values, and the question of what to take. What makes a generated instance useful is knowing the answer, and this one solves each instance exactly by dynamic programming rather than approximating it. Alongside the optimum it shows what taking items by value per unit of weight would get — the intuitive method, which is wrong often enough to be worth demonstrating on a concrete instance rather than describing.
What this generator does
Builds an instance of the 0/1 knapsack problem — each item is taken whole or left — and solves it with a dynamic programme over every capacity up to the limit. The capacity is set near half the total weight, which is where instances are hardest rather than where everything or nothing fits.
How to use this tool
- Choose how many items the instance should have.
- Work out the best selection within the weight limit.
- Reveal the answer to see the optimal set and its value.
- Compare it against the greedy value shown, which is often lower.
Understanding the controls
- How many items
- Between 4 and 16. The upper limit is where an exhaustive check remains affordable, which matters because the tests verify the solver against brute force at that size.
- Seed
- Any word reproduces the same instance exactly, so two people can attempt it independently and compare.
- Show the answer
- Reveals which items the optimal selection takes, its total value, and what the value-per-weight method would have got instead.
Common use cases
- Practice instances for a dynamic programming exercise with known answers
- Demonstrating concretely that value per weight is not a solver
- Testing your own knapsack implementation against a proved optimum
- Teaching material where the answer needs to be checkable in class
- Setting two people the identical instance to compare approaches
How this generator works
The dynamic programme fills a table of best value against items considered and capacity remaining, then walks it backwards to recover which items were taken. That is exact, unlike the ratio heuristic, and it runs in time proportional to items times capacity rather than to two-to-the-items.
Randomness and fairness
The weights, values and item names are random; the optimum is computed, not estimated. Seeded instances are reproducible and are therefore explicitly not cryptographically secure. Without a seed the browser's cryptographically secure generator supplies the draws.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- 0/1 knapsack only — items cannot be split, and the fractional version has a genuinely different answer.
- Weights and values are small whole numbers, which keeps the table affordable but is not what a real instance looks like.
- Sixteen items is the ceiling, because that is where the exhaustive check used to verify the solver stops being cheap.
- There is no visualisation of the table; the answer is given, not the working.
- Instances are not stored, so seed one you want to reuse.
Privacy and your data
Instances are generated and solved entirely in your browser. Nothing about the instance or your seed is transmitted or kept.
Related generators
- Bin Packing Problem GeneratorPacking instances with bins of one size or several at different prices, each with an answer, a lower bound, and a plain statement of when the two meet.
- Travelling Salesman Problem GeneratorTour instances on random coordinates, solved exactly by Held-Karp, with the nearest-neighbour tour shown for comparison.
- Interval Scheduling GeneratorPicks the largest possible set of non-overlapping bookings, and shows how many the obvious first-come rule would have lost.
- Auction Mechanism GeneratorRuns the same private values through a first-price and a second-price auction, proving by enumeration that honest bidding cannot be beaten in the second.
- Integer Partition GeneratorA random way to split a small number into positive whole-number parts.
- Makespan Scheduling Problem GeneratorJobs across identical machines, scheduled longest-first, with two lower bounds that often prove the schedule optimal.