The 0/1 knapsack problem asks you to pick the most valuable subset of indivisible items that fits inside a single whole-number capacity, where every item is used either once or not at all and the optimum is found through an exact dynamic-programming table over items and capacity units. Each row contributes a positive whole-number weight and a non-negative value; the goal is to maximise total value while total weight never exceeds the entered capacity. The "0/1" label is literal — no item is split, repeated, or partially packed, and items heavier than the capacity are rejected rather than silently dropped from consideration. Solving the problem exactly for that bounded case means the result is provably the best possible for those inputs, not just a good guess. The Knapsack Problem Calculator runs that exact 0/1 dynamic program locally and surfaces the chosen labels, total value, used weight, and remaining capacity as plain text you can copy.
What the 0/1 knapsack problem actually asks
The classic formulation treats one container as a scalar capacity and every candidate as an indivisible choice with two attached numbers — a weight and a value. The objective is to maximise total value, the constraint is that total weight stays at or below capacity, and the integrality rule forces each decision variable to be either 0 or 1. Google OR-Tools describes this as choosing a subset whose total value is maximised without exceeding capacity, which is exactly the same model the calculator implements.
Three small details decide whether a given problem fits the 0/1 form. First, the items are indivisible — there is no concept of taking half a server or 30% of a project. Second, the container is a single scalar limit, not a set of equal-size bins, so multi-container problems need a different tool. Third, the optimum is the highest total value; there is no second objective like minimising waste. When those three details hold, the dynamic-programming approach reaches the global optimum in bounded time and memory.
Enter capacity and items into the calculator
The first input is one whole-number capacity from 1 through 10,000. Capacity and weights must both be integers because the dynamic-programming table keeps one state per capacity unit, and decimal weight measurements should be scaled consistently before entry — for example, converting 2.5 kilograms to 25 tenths of a kilogram, knowing that a finer scale increases the table size.
Each item row contains three comma-delimited parts: a label, a positive whole-number weight, and a value. The label cannot contain commas because commas delimit the three fields, and duplicate labels are rejected so the output never names two selected items with the same identifier. Weights larger than the capacity are refused on entry rather than ignored, which makes it explicit that such a row cannot be represented as a selectable candidate under the current limit. Values may be zero or positive decimals and need not use the same unit as weight — value can be priority points, expected profit, or any other scalar you choose, as long as higher value means the more preferred item for the objective.
The list itself is bounded to 100 items to keep browser memory and response time predictable, and the tool rejects blank fields, non-positive weights, non-finite values, and malformed rows outright. These input limits exist so the dynamic-programming table stays small enough to build and walk back inside one tab without freezing.
Run the solver and read every number
- Open the Knapsack Problem Calculator in your browser; nothing is uploaded, the table is built locally in your tab.
- Enter the single whole-number capacity at the head of the form — pick a number between 1 and 10,000 that represents your one container.
- Add each item as a row in label, weight, value format, keeping weights positive integers and labels comma-free and unique.
- Run the solver to build the 0/1 dynamic-programming table over your items and capacity and to backtrack the chosen labels.
- Inspect the result block: read the chosen items, then the total value, the used weight, and the remaining capacity beneath.
- Copy the selection as plain text if you need to paste it into a worksheet, brief, or assignment write-up.
- If you change a label, weight, value, or the capacity, re-run the solver; on equal-value ties the earlier solution is retained, so repeated input reproduces the same answer.
How the dynamic-programming table reaches the optimum
For every item and every capacity from 0 up to the entered limit, the table stores the best total value achievable using only the items considered so far. At each cell it compares two states: the best value without the item, and the best value with the item added to the best compatible earlier state. The larger of the two is retained, which is the standard recurrence for the 0/1 form described in Stanford's CS161 lecture on 0/1 knapsack dynamic programming.
Once the table is complete, the solver walks backward through the recorded decisions to reconstruct the chosen labels. On equal-value ties the earlier solution is retained, so the answer is deterministic: the same inputs always yield the same output. Eight hand-audited golden cases cover exact fills, equal-value ties, decimal values, zero-value items, and the well-known trap where choosing the highest value-to-weight ratio greedily would miss the optimum — for instance, a 10-capacity case in which weight 4 / value 40 plus weight 3 / value 50 reaches value 90 (total weight 7, well under capacity 10), instead of following input order or a naive ratio order.
| Variant | Item rule | Containers | Solver style |
|---|---|---|---|
| 0/1 knapsack (this tool) | Each item chosen once or not at all | One scalar capacity | Exact dynamic programming |
| Fractional knapsack | Items can be split into portions | One scalar capacity | Greedy by value-to-weight ratio |
| Multiple knapsack | Each item at most once | Several distinct capacities | Exact integer programming |
| Bin packing | Each item once, sizes fit bins | Equal-size bins, minimise count | Heuristic (first-fit decreasing) |
The table makes it clear why the same formula will not transfer. A greedy ratio strategy solves the fractional variant but is provably wrong for the 0/1 variant, and equal-size bins change the objective from maximising value to minimising the number of bins used — a different question answered by a bin-packing solver.
Where the 0/1 knapsack model fits in real decisions
Classroom exercises are the obvious use, but the same shape shows up wherever one scalar budget caps a set of indivisible choices. Feature prioritisation against an explicit effort budget, bounded portfolio examples, project selection within a headcount cap, and small allocation drafts all map cleanly onto the 0/1 form as long as the items remain indivisible and the limit stays single.
The model becomes inadequate the moment extra structure enters the problem. The calculator does not know physical dimensions, balance, fragility, mandatory groups, incompatible pairs, deadlines, risk, or uncertainty, and a mathematically optimal scalar selection can still be physically impossible or operationally inappropriate. For financial portfolios, safety loading, medical resource allocation, or other high-stakes decisions, the scalar model is not enough on its own; the objective, dependencies, and constraints should be reviewed against an appropriate domain model by an accountable reviewer before any commitment is made.
For readers who want the contrast with the greedy variant, the fractional knapsack step-by-step guide walks through the same shape with item splitting allowed, which is a useful sanity check on why ratio order is not enough when items are 0/1.
For a deeper look, see How to Solve the Pythagorean Theorem for a Right Triangle.