The 0/1 knapsack problem is calculated by building a dynamic-programming table over items and capacity, keeping the larger of two states at every cell: the best value without the current item, and the best value when it is added on top of an earlier selection that fits the remaining weight. For capacity C and n items with whole-number weights, the table has (n+1) × (C+1) cells and each cell stores the maximum reachable value for that prefix and capacity. After the table is filled the solver walks backward through the decisions it recorded to reconstruct the chosen labels. Because every cell stores a proven maximum for a smaller sub-problem, the final cell of the final row is provably the global optimum for the bounded 0/1 model — not an approximation, not a heuristic, and not a guess. The same dynamic-programming scheme is documented in Google OR-Tools' knapsack reference and in Stanford CS161's lecture notes on 0/1 knapsack dynamic programming. A practical way to apply this calculation is the Knapsack Problem Calculator, which runs the same DP locally, enforces whole-number capacity and weights, and reports exactly which items were selected along with the totals.
The exact mechanics of the 0/1 calculation
The 0/1 knapsack problem is a single-container selection: given n items, each with a positive integer weight w_i and a nonnegative value v_i, and a single capacity C, maximize the total value Σ v_i · x_i subject to Σ w_i · x_i ≤ C with x_i ∈ {0, 1}. Each item is either excluded or selected once — it cannot be split, repeated, or partially packed. The DP table expresses this constraint pair (item index, remaining capacity) at every cell.
The state at dp[i][c] is the maximum total value reachable using the first i items while staying within capacity c. The transition compares two choices: skip item i and keep dp[i-1][c], or take item i (valid only when w_i ≤ c) and inherit dp[i-1][c - w_i] plus v_i. The larger value is stored, along with the decision that produced it for later backtracking. When w_i > c the only legal choice is to skip, so dp[i][c] reduces to dp[i-1][c].
Complexity is O(n · C) time and O(C) memory after row compression, which is why the model runs fastest on small whole-number weights. Greedy heuristics that pick items by value-to-weight ratio fail on cases the DP handles exactly. The Google OR-Tools reference describes the identical objective as "choosing a subset whose total value is maximized without exceeding capacity," and the underlying table-walk mechanics are spelled out in Stanford CS161's lecture on the 0/1 DP.
0/1 knapsack versus neighbouring models
Before you calculate, make sure 0/1 knapsack is actually the model you need. The differences are small in wording but large in outcome.
| Variant | Containers | Item usage | Splits allowed | Common solver |
|---|---|---|---|---|
| 0/1 knapsack (this calculator) | 1 | 0 or 1 time each | No | Exact DP |
| Fractional knapsack | 1 | Any fraction, continuous | Yes | Greedy by ratio |
| Multiple knapsack | Several, each with a limit | 0 or 1 per bin | No | Branch-and-bound, ILP |
| Bin packing | Many equal bins | 0 or 1 per bin | No | FFD / BFD heuristics |
| Unbounded knapsack | 1 | Unlimited copies | No | 1-D DP with repeated weights |
If your problem involves two or more containers, items that can repeat, or fractions of an item, this calculator will not model it accurately. For the multi-container case, the Bin Packing Calculator packs labelled sizes into equal-capacity bins with deterministic first-fit-decreasing placement, which is a related but distinct objective.
How to calculate a knapsack problem step by step
- Open the Knapsack Problem Calculator and enter one whole-number capacity from 1 through 10,000 in the capacity field.
- Add each item as a new row using the label, weight, value format. Weights must be positive whole numbers; values may be zero or positive decimals. Do not put commas in labels, because commas separate the three fields.
- Stop adding rows when you have listed every candidate. The tool accepts up to 100 unique labelled items and rejects duplicates by label.
- Click Solve. The calculator validates the inputs, builds the DP table in the browser, and backtracks the chosen items. The selected labels, total value, total weight, and remaining capacity appear in the result panel.
- Inspect every selected item and confirm the listed assumptions before copying the selection. The copy button places plain text on your clipboard for use in notes or spreadsheets.
If your inputs include a fixed-decimal measurement — for example, 2.5 kilograms — multiply by 10 (or 100) consistently before entry so the weight stays a whole number. A finer scale creates a larger table, which is why the calculator caps capacity at 10,000 and the item list at 100 rows. Exact figures for any specific scenario are produced by running that input through the calculator rather than computed by hand.
Worked example: a 10-capacity case
To see the calculation in action, take capacity C = 10 and three candidate items: Crystal (weight 4, value 40), Module (weight 3, value 50), and Heavy (weight 9, value 89).
Step 1 — Row 0 is the empty prefix: dp[0][w] = 0 for every capacity 0..10.
Step 2 — Row 1 (Crystal, 4/40). At w = 10 we have dp[1][10] = max(dp[0][10] = 0, 40 + dp[0][6] = 40) = 40, so the table records "include Crystal."
Step 3 — Row 2 (Module, 3/50). At w = 10 we have dp[2][10] = max(dp[1][10] = 40, 50 + dp[1][7] = 50 + 40 = 90) = 90, so Module is included and the backtrack returns to dp[1][7], which itself was "include Crystal."
Step 4 — Row 3 (Heavy, 9/89). At w = 10 we have dp[3][10] = max(dp[2][10] = 90, 89 + dp[2][1] = 89 + 0 = 89) = 90. Heavy is excluded and the previous optimum is kept.
Final state: dp[3][10] = 90 with total weight 4 + 3 = 7, leaving 3 units of unused capacity. The naive greedy choice of Heavy alone would have returned 89 against weight 9. The DP finds the strict improvement by considering every pairing, not by ratio ordering.
| Strategy | Selected labels | Total value | Total weight | Proven optimum? |
|---|---|---|---|---|
| Greedy: largest item that fits first | Heavy | 89 | 9 of 10 | No — misses the better pair |
| Greedy: highest value-to-weight ratio first | Module + Crystal | 90 | 7 of 10 | Coincidental — not provable |
| Exact 0/1 dynamic programming | Module + Crystal | 90 | 7 of 10 | Yes — proven maximum |
This exact input is one of the eight golden test cases shipped with the Knapsack Problem Calculator, designed to confirm the solver never falls back to a highest-value-to-weight heuristic on a deceptive input order.
How to interpret the calculator's output
Once the Knapsack Problem Calculator finishes, four numbers tell you the entire story: the chosen item list, the total value (the figure the DP proved maximal), the total weight (always ≤ capacity — the test suite asserts this), and the remaining capacity. Reading them in order prevents most mis-uses.
If two distinct subsets share the same maximum value, the tool keeps the earlier solution rather than switching arbitrarily — that is, the first label set the DP recorded for the tie. With the same input repeated, this determinism lets you compare scenarios by changing one row at a time and diffing the outputs.
A common misinterpretation is to read the result as a physical packing plan. The table has no concept of shape, balance, or fragility, so a "perfect" value-maximising selection may still not fit a real container. Treat the output as a value-maximising selection under one scalar cost, and bring in physical constraints separately.
Limits the calculator enforces — and what it deliberately ignores
Several inputs are rejected rather than silently ignored, so the answer is never a phantom optimum: blank fields, duplicate labels, commas inside a label, malformed comma-separated rows, nonpositive weights, non-finite values such as NaN or missing text, and weights greater than the entered capacity. An item heavier than the capacity is returned as a validation error rather than dropped, which makes it clear that the input cannot be represented as a selectable candidate under the current capacity.
Equally important is what the model does not know. The DP does not model physical dimensions, balance, fragility, item interactions, mandatory groups, incompatible pairs, deadlines, or uncertainty. Eight hand-audited test cases verify that selected weight never exceeds capacity and that exact fills, equal-value ties, decimal values, and zero-value items all behave correctly.
For high-stakes uses — financial portfolios, safety loading plans, medical resource allocation — the scalar 0/1 model is necessary but not sufficient; the objective, the dependencies between items, and the real-world consequences must still be validated by an appropriate domain model and accountable reviewer before the selection is acted on.