0/1 knapsack selection
Choose indivisible items to maximize total value within an integer weight capacity using exact dynamic programming.
The example value has been entered. Check it immediately or change the value.
Input is processed in the browser. Refreshing returns a sample value.
Instructions and example
DPᵢ(c)=max(DPᵢ₋₁(c),DPᵢ₋₁(c−wᵢ)+vᵢ); xᵢ∈{0,1}
For weight,value 2,3 / 3,4 / 4,5 and capacity 5, rows 1,2 yield weight 5 and value 7.
At most 100 items; integer weights 1–10,000, values 0–1,000,000 and capacity 0–10,000. Repeated selection and fractional items are not allowed. Floating-point results display at most 12 significant digits.
Frequently asked questions
How can several identical items be selected?
Enter separate rows for the available copies. Each row can be selected once and results use row numbers.
Must the knapsack capacity be filled exactly?
No. Total value is maximized at or below capacity; unused capacity can be optimal.
Calculation criteria and reference materials
- Google OR-Tools: knapsack
Indivisible item selection under a capacity constraint.
Verification of calculation criteria: · Calculation·verification principles · Report errors