Knapsack Solver
One item per line as "weight,value" - pick the knapsack type and capacity to get the highest-value combination
Knapsack type:
Capacity:
Calculation Result
Download CSV
| No. | Item | Weight | Value | Picked count |
|---|
Introduction to the tool and how to use it
A knapsack problem solver that answers "what should I pack to get the most value". Enter one item per line in
How to use:
1. Pick the knapsack type:
- 0/1 knapsack: each item can be taken at most once;
- Unbounded knapsack: each item can be taken any number of times;
2. Set the capacity (a whole number; decimals are rounded with a notice);
3. Hit Run - the table shows the pick count of every item plus a summary row, and the text box repeats the summary;
4. Copy the result or export it as CSV.
It uses the classic one-dimensional dynamic programming: reverse rolling for the 0/1 knapsack and forward rolling for the unbounded one, with backtracking data so the reported combination really reaches the optimal value instead of just giving a number. Capacity is capped at 100,000 and the item count at 500 - anything beyond that is clamped with a notice instead of freezing the browser.
weight,value form, for example:3,54,62,35,9How to use:
1. Pick the knapsack type:
- 0/1 knapsack: each item can be taken at most once;
- Unbounded knapsack: each item can be taken any number of times;
2. Set the capacity (a whole number; decimals are rounded with a notice);
3. Hit Run - the table shows the pick count of every item plus a summary row, and the text box repeats the summary;
4. Copy the result or export it as CSV.
It uses the classic one-dimensional dynamic programming: reverse rolling for the 0/1 knapsack and forward rolling for the unbounded one, with backtracking data so the reported combination really reaches the optimal value instead of just giving a number. Capacity is capped at 100,000 and the item count at 500 - anything beyond that is clamped with a notice instead of freezing the browser.
Message board
All messages →-
No one has spoken up yet — want to go first?