Knapsack problem solver: pick the most valuable items within a limit
Each item is taken or not (a yes/no decision), and the items taken must fit within a limit such as a weight, a budget or hours. Change the values, weights and limit below and solve, no account needed. The answer is proven optimal by an integer programming solver.
Solve it here
The example below is the 0-1 knapsack problem worked example; its saved answer, checked by the solver, is 22 (optimal).
How to type it
- First line:
maximizeorminimizeand the objective, such as3*a + 2*b. - Then
subject toand one constraint per line with<=,>=or=. a, b >= 0for nonnegative variables;integer: aorbinary: zfor whole-number or yes/no ones.- Lines starting with
#are notes, such as what a variable means.
What you get here
- which items to take (1 = take, 0 = leave) and their total value
- a check that the limit is respected
- the proof label from the integer programming solver
With a free account: the full step-by-step walkthrough, word problems, photos and voice, and your history.
Worked examples
Questions
Can an item be taken more than once?
Yes: write integer: t1 with t1 >= 0 and a bound such as t1 <= 3, instead of binary: t1.
Can there be two limits, such as weight and volume?
Yes: add one constraint line for each limit.
More: all calculators · 50 solved examples · what the app solves
Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.