Online Tool Store
Knapsack Solver
Solve the 0/1 knapsack problem — pick the highest-value set of items that fits a weight or budget limit — with the chosen set explained.
🔒 This tool runs entirely in your browser. Your files are never uploaded to a server.
Math & Science
Knapsack Solver
Frontend preview — no upload or external service.
Optimal selection
12 kg capacity, 14 candidate items: optimal set is 7 items totalling 11.8 kg and 268 value. The greedy value-per-kg choice would have scored 251.
How the Knapsack Solver works
- List each item with its weight (or cost) and the value you assign it.
- Set the capacity — a pack weight limit, a budget, a time box.
- Compare the optimal set against your instinctive choice; the difference is usually one item you would have taken and shouldn't.
The method
The 0/1 knapsack takes or leaves each item whole, and is solved exactly by dynamic programming over capacity.
maximise Σ value subject to Σ weight ≤ capacity, each item taken 0 or 1 times
Picking greedily by value-per-weight is fast and not optimal for 0/1 — it is optimal only in the fractional version where items can be split.
FAQ
Why isn't picking the best value-per-weight optimal?
Because items are indivisible. A slightly worse ratio item may fill the remaining space perfectly where the better one does not fit at all. Greedy is optimal only when items can be split.
What is this actually used for?
Packing decisions, budget allocation across projects, cargo loading, and cutting stock problems. Anything where you choose a subset under a single hard limit has this shape.
Is the problem hard?
It is NP-hard in general, but dynamic programming solves it efficiently when capacities are integers of moderate size, which covers most practical uses.
How we compare
| Feature | Online Tool Store | A graphing calculator | A stats package |
|---|---|---|---|
| Exact optimal solution | ✓ | Greedy guess | Yes |
| Compares against greedy | ✓ | ✗ | Sometimes |
| No solver software | ✓ | ✓ | ✗ |
| Data stays local | ✓ | ✓ | ✗ |
Knapsack Solver shows what the greedy choice would have scored, which is the clearest demonstration of why value-per-weight is not optimal.