Knapsack 0/1 Calculator (Combinatorial Optimization)

Knapsack 0/1, fractional and bounded calculator: dynamic programming, greedy, value/weight efficiency comparison, FPTAS overview and solution reconstruction.

Calculation parameters
Was this calculator useful?

The knapsack problem

The knapsack problem is one of Karp's original 21 NP-complete problems (1972) and a cornerstone of combinatorial optimization. Given a collection of items each with weight and value, and a knapsack of capacity W, determine the subset maximizing total value without exceeding capacity. Main variants are 0/1 (each item taken whole or not), fractional (fractions allowed), and bounded (limited copies).

Mathematical formulation

Maximize Sigma v_i * x_i subject to Sigma w_i * x_i = V exist?" is NP-complete; optimization is NP-hard. Pseudo-polynomial O(nW) algorithms exist via dynamic programming.

Dynamic programming

The classic algorithm builds dp[i][w] = max value using first i items with capacity w. Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i) if w_i <= w, else dp[i-1][w]. Base case dp[0][w] = 0. Optimal solution is dp[n][W]; chosen items recovered by backtracking comparing dp[i][w] and dp[i-1][w]. Complexity O(nW) time, O(nW) space (reducible to O(W) with reverse iteration).

The four modes

  1. Solve 0/1: classic dynamic programming with optimal solution reconstruction.
  2. Fractional: greedy algorithm sorting by v/w descending and filling until capacity exhausted.
  3. Bounded: each item has max quantity q_i. Implemented via binary decomposition reducing to 0/1 with O(log q_i) copies.
  4. Efficiency comparison: computes value/weight ratio per item, useful to intuit greedy solution.

Greedy fails on 0/1

Sorting by v/w descending solves fractional but can be arbitrarily suboptimal for 0/1. Example: W=10, items [(6,60), (5,50), (5,50)]. Greedy picks first (ratio 10) leaving W=4 unused: value 60. Optimum picks last two: value 100. Modified greedy (max of greedy vs best single item) guarantees 1/2 of optimum.

Approximation: FPTAS

A fully polynomial approximation scheme (FPTAS) exists for 0/1 knapsack: for every epsilon>0, O(n^3/epsilon) algorithm returning value >= (1-epsilon) * OPT. Obtained by scaling values by v_max*epsilon/n and applying DP keyed on values instead of weights.

Classic example

W=10, items: (w=2, v=3), (w=3, v=4), (w=4, v=5), (w=5, v=6). DP yields dp[4][10] = 13 selecting items 1, 2, 4 (weights 2+3+5=10, values 3+4+6=13). Use as benchmark to verify code.

Real applications

  • Budget allocation: project selection with maximum ROI under budget constraint.
  • Cutting stock: optimization in textile, paper, metal cutting.
  • Portfolio optimization: stock selection with capital limit.
  • Container loading: sea and air logistics.
  • Cloud computing resource allocation: VM placement on hosts with RAM/CPU limits.
  • Fixed-bitrate lossy data compression.

History of the knapsack problem

The knapsack problem takes its name from the intuitive situation of someone who must fill a bag of limited capacity by choosing, among many objects, those of maximum total value. Formalised in operations research in the mid-twentieth century, it became one of the most studied problems in theoretical computer science. In 1972 Richard Karp included it in his famous list of 21 NP-complete problems, sealing its intrinsic difficulty. The problem also played a historical role in cryptography: in 1978 Ralph Merkle and Martin Hellman proposed one of the first public-key cryptosystems based on the knapsack (the Merkle-Hellman knapsack). The idea was to use the problem's difficulty as a security guarantee, but the system was spectacularly broken by Adi Shamir in 1982, who exploited its special structure. Since then the knapsack has remained a fundamental testbed for exact, heuristic and approximation algorithms.

Why the algorithm is pseudo-polynomial

Dynamic programming solves 0/1 knapsack in time O(n·W), where n is the number of items and W the capacity. At first sight it seems efficient, but there is a subtle detail: W is a numerical value, not the size of the input. To represent the capacity W only about log₂(W) bits are needed, so the time O(n·W) is exponential in the length of the input data. This is what is meant by a pseudo-polynomial algorithm: polynomial in the value of the numbers, but exponential in the number of digits. This is why knapsack is weakly NP-hard: if capacities and weights stay small, the DP is very fast, but with huge numbers (hundreds of digits) it becomes impractical. A truly polynomial algorithm in the input size is not known, and its existence would amount to proving P = NP.

Updated July 2026

Frequently Asked Questions

Why is 0/1 knapsack NP-hard if DP is O(nW)?

Because O(n·W) is pseudo-polynomial, not polynomial. W is a numerical value represented by about log₂(W) bits, so relative to the actual input length the time is exponential. With small weights and capacities the DP is very fast, but if the numbers have hundreds of digits it becomes impractical. The knapsack's NP-hardness is weak precisely because it is tied to the magnitude of the numbers, not the number of items.

When to use DP vs greedy?

Dynamic programming gives the exact optimal solution of the 0/1 problem, but costs O(n·W): it is worthwhile when the capacity is moderate. The greedy approach by value/weight is very fast (O(n log n)) but gives the optimum only for the fractional knapsack, where items are divisible. On the 0/1 problem greedy can be very wrong. Greedy is used only for quick estimates or as a starting heuristic.

How does binary decomposition work for bounded?

In the bounded problem each item has a maximum available quantity. Instead of duplicating it many times, it is split into groups of size 1, 2, 4, 8, ... (powers of two), plus a remainder. With these bundles any quantity up to the maximum can be composed, and the problem reduces to a 0/1 knapsack with log(Qmax) extra items per article. This lowers the cost from O(n·W·Qmax) to O(n·W·log Qmax), a huge gain.

Is there a better algorithm than O(nW)?

For the general case no algorithm polynomial in the input size is known, and finding one would prove P = NP. There are, however, fully polynomial approximation schemes (FPTAS) that, accepting a small relative error ε, guarantee a solution within (1−ε) of the optimum in time polynomial in n and 1/ε. In practice branch-and-bound algorithms are also used, which, exploiting upper bounds, solve large instances much faster than the worst case.

Is multidimensional knapsack (MKP) much harder?

Yes. In the multidimensional knapsack each item has several cost attributes (weight, volume, etc.) and there are several capacity constraints to satisfy simultaneously. Dynamic programming would need a table with one dimension per constraint, blowing up memory and time. The problem stays NP-hard and no longer admits a simple FPTAS: in practice it is tackled with integer linear programming, metaheuristics or sophisticated branch-and-bound algorithms.

How to handle divisible items in practice?

If items are divisible, one switches to the fractional knapsack, solved optimally with a simple greedy: items are sorted by decreasing value/weight ratio and the bag is filled starting from the most efficient, taking a fraction of the last item to exactly fill the capacity. This is the typical case of continuous materials such as liquids, powders or meltable precious metals, and unlike the 0/1 case greedy is here rigorously optimal.

Does knapsack reduce to SUBSET-SUM?

SUBSET-SUM is a special case of the knapsack in which each item's value equals its weight and one asks whether a subset reaches exactly the capacity. It is itself NP-complete, and its reduction to the knapsack shows the latter's difficulty. Both share the same pseudo-polynomial structure: the DP on SUBSET-SUM costs O(n·S), where S is the target sum, with the same applicability limit as the knapsack.

What is the knapsack problem used for in practice?

It is everywhere in problems of optimal allocation of limited resources: in the selection of investments under a fixed budget (capital budgeting), in cutting materials to minimise waste, in loading containers and aircraft, in production planning and in project selection. It also appears in historical cryptography, in memory management and in recommender systems, wherever a value must be maximised subject to a capacity constraint.

Comments (0)

No comments yet. Be the first!