The 0/1 Knapsack Problem is a classic combinatorial optimisation problem: given n items each with a weight wᵢ and a value vᵢ, select a subset that maximises total value without exceeding a weight capacity W. The "0/1" label indicates each item must be taken entirely or not at all — no fractional selection is permitted. The problem is NP-hard, meaning no known polynomial-time algorithm solves all instances, but the dynamic programming (DP) approach runs in O(nW) pseudo-polynomial time and finds the exact optimum.
In this simulation you can add, edit, or remove items and watch the DP table fill cell by cell: each cell dp[i][w] stores the maximum value achievable using the first i items with capacity w. After the table is complete, a backtracking phase traces the optimal item selection highlighted in the grid, and a side-by-side comparison shows how the greedy fractional heuristic differs from the DP exact solution.
What is the recurrence relation for the 0/1 knapsack DP?
dp[i][w] = max(dp[i−1][w], dp[i−1][w − wᵢ] + vᵢ) if wᵢ ≤ w, else dp[i−1][w]. The first term skips item i; the second takes it (only possible if its weight fits). The base case is dp[0][w] = 0 for all w. The final answer is dp[n][W].
Why is the 0/1 knapsack problem called NP-hard?
NP-hardness means that no polynomial-time algorithm is known that solves all instances. The DP approach runs in O(nW) time, but W itself can be exponentially large in its binary representation (pseudo-polynomial, not truly polynomial). The problem was shown NP-complete by reduction from the subset-sum problem by Karp in 1972. In practice, for moderate W (up to millions), the DP is entirely feasible.
How does greedy fractional knapsack differ from the 0/1 version?
The fractional knapsack allows items to be split; the greedy strategy of always picking the item with the highest value-to-weight ratio (vᵢ/wᵢ) gives the optimal solution in O(n log n) time. For 0/1 knapsack, this greedy approach can fail: e.g., with capacity 10, items (weight 6, value 6) and (weight 5, value 5) and (weight 5, value 5), the ratio-greedy picks item 1 for value 6, but taking items 2 and 3 gives value 10.
Starting from cell dp[n][W], compare it with dp[n−1][W]. If they differ, item n was included; subtract its weight from W and move to row n−1. If they are equal, item n was excluded; move to dp[n−1][W]. Repeat until row 0. This backtracking pass runs in O(n) time.
Yes. Because dp[i][w] only depends on row i−1, you can use two 1D arrays of length W+1 (current and previous row), reducing space to O(W). If you iterate w from W down to wᵢ in a single 1D array, you can achieve O(W) space in-place without storing previous rows, though backtracking then requires re-computation or storing row differences.
Branch-and-bound explores the exponential search tree of include/exclude decisions but prunes subtrees whose upper bound (typically the fractional relaxation) cannot beat the current best solution. For many practical instances this is much faster than DP when W is huge but n is small. It is the basis of commercial integer-programming solvers like Gurobi and CPLEX.
Yes. A Fully Polynomial-Time Approximation Scheme (FPTAS) produces a solution within factor (1 − ε) of optimal in O(n²/ε) time, by scaling and rounding item values. This makes the DP table small enough for large W while guaranteeing near-optimal results, and is a landmark result in approximation theory.
Applications include cargo loading (maximising revenue subject to aircraft weight limits), resource allocation (allocating CPU/memory among competing jobs), portfolio selection (maximising returns subject to a budget), cryptography (early knapsack-based public-key schemes by Merkle-Hellman, now broken), and compiler register allocation.
In the multiple-knapsack problem there are m knapsacks each with its own capacity, and items must be assigned to at most one knapsack. This generalises bin packing and is strictly harder; optimal solutions require integer linear programming or heuristics such as first-fit-decreasing. It arises in logistics, cloud VM bin-packing, and cutting-stock problems.
In the unbounded variant, each item can be chosen any number of times (unlimited supply). The recurrence changes to dp[w] = max over all i where wᵢ ≤ w of (dp[w − wᵢ] + vᵢ), using a single 1D array iterated forward from w = 1 to W. This models scenarios like coin-change or cutting a rod into pieces to maximise profit.