Enter items and capacity, then run the solver. Choose best-first or depth-first exploration mode quickly. See optimal value, chosen items, and pruning statistics below.
Use this sample to verify the solver output and exports.
| Item | Value | Weight | Value/Weight |
|---|---|---|---|
| A | 40 | 2 | 20.000 |
| B | 30 | 5 | 6.000 |
| C | 50 | 10 | 5.000 |
| D | 10 | 5 | 2.000 |
| E | 35 | 7 | 5.000 |
Capacity: 16. A common optimal set is A + B + E (value 105, weight 14), but your run depends on sort and limits.
This solver targets the 0/1 knapsack objective: maximize Σ vᵢ xᵢ subject to Σ wᵢ xᵢ ≤ C, where xᵢ ∈ {0,1}.
Branch-and-bound explores include/exclude decisions per item. Each node gets an upper bound using a fractional knapsack relaxation: fill remaining capacity with whole items, then one fractional item, using the chosen sort order. Nodes with bound ≤ best are pruned.
This calculator solves the 0/1 knapsack model, where each item is either chosen or rejected. The objective is to maximize total value while respecting a strict capacity limit. It is widely used to model selection under constraints, such as budgeted projects, limited storage, or fixed processing windows. Because the decision variables are binary, the problem is combinatorial, and exact solutions benefit from intelligent pruning for realistic input sizes.
Branching creates a decision tree: at level i, the algorithm tries including item i and excluding item i. Bounding assigns an optimistic upper limit to each partial decision so unpromising branches can be discarded early. This reduces the search dramatically compared with enumerating all 2^n subsets.
The bound here is computed with a fractional knapsack relaxation. After placing the already-fixed items, the remaining capacity is filled greedily with whole items in the selected sort order, and then with a fraction of the next item. The resulting value is an admissible upper bound for the true 0/1 optimum below that node.
Best‑first prioritizes the node with the highest bound, often finding strong solutions quickly and pruning aggressively once a good incumbent exists. Depth‑first dives deeper using a stack, which can be memory‑light and fast for small instances, but may explore weaker branches longer before tightening the incumbent.
Nodes created count all generated states, expanded counts states that actually branched, and pruned counts states discarded by the bound rule. The displayed “gap” equals the last seen upper bound minus the best feasible value found. A zero gap with completed search indicates optimality.
Keep weights positive, scale units consistently, and avoid extreme magnitudes that obscure comparisons. For larger lists, start with density sorting and best‑first exploration, then raise node and time limits gradually. Export the CSV to audit the node trace and reproduce results in reports.
It solves a 0/1 knapsack selection: choose a subset of items to maximize value without exceeding the capacity constraint.
If the search stops due to node or time limits, the best solution is feasible but optimality is not mathematically guaranteed.
Enter one item per line as name,value,weight. You may also use two numbers as value weight.
It is an optimistic estimate from a fractional relaxation. If the bound is not better than the best found value, that branch is pruned.
Best-first often finds strong incumbents quickly and prunes earlier. Depth-first can be simpler and memory-light for small inputs.
Sorting affects the fractional bound quality and node ordering. Better bounds prune earlier, reducing explored nodes and improving runtime.
Important Note: All the Calculators listed in this site are for educational purpose only and we do not guarentee the accuracy of results. Please do consult with other sources as well.