In the 0/1 knapsack problem, xi is a binary decision variable equal to 1 when item i is packed and 0 when it is left out, and the goal is to find the xi values that maximize total value without exceeding the container's capacity. The standard formulation writes the objective as the sum over i of vi·xi, with the constraint that the sum over i of wi·xi must be less than or equal to C, the single container capacity. Because every item is indivisible, each xi must be 0 or 1 — there is no 0.5 or 0.7 — and you cannot pick the same item twice. The set of all xi values for n items is the solution vector X = (x1, x2, …, xn), and finding X is the same task as naming the optimal subset. You can build a dynamic programming table indexed by item and capacity, then backtrack through the recorded decisions to read off which xi were set to 1. The Knapsack Problem Calculator automates this exact procedure and returns each selected label with total value, total weight, and the unused capacity.
What Xi Represents in the 0/1 Knapsack Problem
Each xi is a binary switch that controls whether item i enters the knapsack. When you write out the solution, every variable in the vector X = (x1, x2, …, xn) is either 0 or 1, never a fraction. A value of 0 means item i stays out of the container; a value of 1 means item i is taken whole. The constraint that xi cannot take other values is what makes this the "0/1" version of the problem rather than the fractional version.
Once you read the xi values, you immediately know the subset: include every index i with xi = 1 and exclude every index i with xi = 0. The subset and the X vector are two ways of describing the same answer. The Knapsack Problem Calculator presents the answer as a list of selected labels, and each label in that list corresponds to an xi value of 1 in the underlying solution.
| Xi value | Meaning | Effect on total weight | Effect on total value |
|---|---|---|---|
| 0 | Item i is excluded | wi is not counted | vi is not counted |
| 1 | Item i is selected whole | wi is added once | vi is added once |
The Mathematical Formulation with Decision Variables
The standard integer program uses xi as the decision variable, wi as the positive whole-number weight of item i, vi as its nonnegative value, and C as the single whole-number capacity. The model is:
Maximize Σ(i=1 to n) vi·xi Subject to Σ(i=1 to n) wi·xi ≤ C xi ∈ {0, 1} for every i
This formulation is the one Google OR-Tools describes as choosing a subset whose total value is maximized without exceeding capacity (Google OR-Tools — The Knapsack Problem). It is the canonical single-container 0/1 model and is the exact model the Knapsack Problem Calculator solves.
| Variant | Decision variable range | Can items be split? | Container count |
|---|---|---|---|
| 0/1 knapsack | xi ∈ {0, 1} | No — taken whole or left out | One |
| Fractional knapsack | xi ∈ [0, 1] | Yes — any portion allowed | One |
| Multiple knapsack / bin packing | xi ∈ {0, 1} | No — taken whole or left out | Several equal containers |
These three problems look similar but ask different questions. Only the 0/1 row matches what the calculator returns. If your real situation allows splitting an item, or if you have more than one container, the xi values the tool reports are not the answer you need.
Solving for Xi with the Dynamic Programming Recurrence
The exact way to find every xi for a single-capacity 0/1 problem with whole-number weights is dynamic programming over a two-dimensional table. Let DP[i][c] be the maximum total value achievable using only the first i items with capacity c. The recurrence compares two cases for each cell:
DP[i][c] = max(DP[i−1][c], DP[i−1][c − wi] + vi)
The first term represents excluding item i (so xi = 0). The second term represents including item i (so xi = 1) and adds vi to the best value achievable with capacity c − wi from the first i − 1 items. The larger of the two terms is retained. This recurrence is the standard treatment for the 0/1 problem (see Stanford CS161 — 0/1 Knapsack Dynamic Programming).
After the table is filled in for i = 1 … n and c = 0 … C, you recover the xi values by walking backward from DP[n][C]. At step i with remaining capacity c, compare DP[i][c] against DP[i−1][c]. If they are equal, item i was excluded and xi = 0, and c stays unchanged. If DP[i][c] is strictly larger, item i was included and xi = 1, and you reduce c by wi before moving to item i − 1. This backtrack produces the full solution vector X in one pass.
One detail matters when two cells tie: equal-value ties retain the earlier solution rather than switching arbitrarily, so the same input always produces the same xi values. This determinism is what makes the calculator's output reproducible across runs.
How to Find Xi Using the Knapsack Problem Calculator
- Enter a whole-number capacity from 1 through 10,000 in the capacity field. Use the same weight unit for every item — for example, all kilograms or all grams.
- Add each indivisible item as a row in the order label, weight, value, using a positive whole-number weight. If your measurements have fixed decimals, scale them consistently before entry (for example, convert 2.5 kg to 25 tenths) and remember that a finer scale creates a larger table.
- Check that no two rows share the same label, since duplicate labels are rejected, and that no weight exceeds the capacity you entered — items heavier than the capacity are rejected rather than silently ignored.
- Solve the exact 0/1 model. The calculator builds the standard dynamic programming table over items and capacity, retains exclusion on exact value ties, and backtracks the maximum-value selection.
- Inspect every selected item and assumption in the result. The output identifies every chosen label, total value, total weight, and unused capacity. Each label in that output corresponds to an xi = 1; every label absent from the output corresponds to an xi = 0.
- Copy the selection as plain text if you need to paste the subset or the totals into a report, a spreadsheet, or a homework solution.
Worked Example: Finding Xi for a Four-Item Problem
Consider four items with whole-number weights and values, and a container of capacity 10.
- Item A: weight 4, value 40
- Item B: weight 3, value 50
- Item C: weight 5, value 60
- Item D: weight 2, value 30
The DP recurrence compares including and excluding each item. After item A is processed alone, the best value at capacity 10 is 40 (taking A: weight 4 ≤ 10, value 40). For item B at capacity 10, including B uses 3 units and combines with the best from {A} at capacity 7, which is 40, giving 40 + 50 = 90. Excluding B keeps DP at 40, so the table retains 90. Continuing through items C and D, the maximum value reachable at capacity 10 is 140, achieved by selecting items B, C, and D together: weight 3 + 5 + 2 = 10 and value 50 + 60 + 30 = 140.
Reading off the xi values from this optimum gives the solution vector X = (0, 1, 1, 1), so xA = 0, xB = 1, xC = 1, xD = 1. Total weight is 10, which equals the capacity, and 10 − 10 = 0 units of capacity remain unused. The Knapsack Problem Calculator reproduces this exact result for the same inputs.
Limits of the Scalar Model and When Xi Alone Is Not Enough
The xi values returned by the calculator are mathematically optimal only inside the stated 0/1 model: one capacity, whole-number weights, nonnegative values, and each item available once. The tool deliberately does not model physical dimensions, balance, fragility, item interactions, mandatory groups, incompatible pairs, deadlines, risk, or uncertainty, so a scalar-optimal selection can still be physically impossible or operationally inappropriate.
Capacity and weights must be whole numbers because the dynamic programming table has one state per capacity unit. The list is capped at 100 unique labels and the capacity is capped at 10,000 to keep browser memory and response time bounded. Values may be zero or positive decimals and need not share the unit of the weight. Blank fields, duplicate labels, nonpositive weights, weights larger than the capacity, non-finite values, and malformed comma-separated rows are rejected rather than silently fixed.
Use the result for classroom problems, feature prioritization with an explicit effort budget, bounded portfolio examples, or small allocation drafts. For financial portfolios, safety loading, medical resource allocation, or other high-stakes decisions, the scalar 0/1 model is insufficient — validate the objective, dependencies, constraints, and real-world consequences with an appropriate domain model and an accountable reviewer before acting on the xi values.
For a deeper look, see How to Solve the Assignment Problem in Excel.