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.

Result

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

Verification of calculation criteria: · Calculation·verification principles · Report errors