The Knapsack Problem

Problem. $n$ items, item $i$ has weight $w_i$ and value $v_i$. Choose a subset of total weight $\le W$ maximising the total value.

NP-hard, but only weakly — the $O(nW)$ DP is polynomial in the value of $W$, not in its number of bits. That is exactly why an FPTAS exists.

The DP — $O(nW)$

$dp[w]=\max (dp[w],dp[w-w_i]+v_i)$

with the weight loop running downward so each item is used once.

long long knapsack(int n, int W, vector<int>& w, vector<long long>& v) {
    vector<long long> dp(W + 1, 0);
    for (int i = 0; i < n; i++)
        for (int cap = W; cap >= w[i]; cap--)
            dp[cap] = max(dp[cap], dp[cap - w[i]] + v[i]);
    return dp[W];
}

$O(nW)$ time, $O(W)$ space. See Knapsack for the full family.

When $W$ is huge but the values are small

Invert the DP: index by value, store the minimum weight.

long long V = accumulate(v.begin(), v.end(), 0LL);
vector<long long> dp(V + 1, LLONG_MAX / 2);
dp[0] = 0;
for (int i = 0; i < n; i++)
    for (long long val = V; val >= v[i]; val--)
        dp[val] = min(dp[val], dp[val - v[i]] + w[i]);
for (long long val = V; val >= 0; val--) if (dp[val] <= W) return val;

$O(n\sum v)$. Always check which of $W$ and $\sum v$ is smaller — the constraints usually make one of them tractable, and this inversion is the intended solution surprisingly often.

The decision table

Situation	Method	Cost
$nW\le 10^8$	standard DP	$O(nW)$
$n\sum v\le 10^8$	value-indexed DP	$O(n\sum v)$
Boolean (subset sum)	bitset	$O(nW/64)$
$n\le 40$, both huge	meet in the middle	$O(2^{n/2})$
Items divisible	greedy by $v/w$	$O(n\log n)$
Unbounded copies	weight loop upward	$O(nW)$
$c_i$ copies each	binary splitting	$O(nW\log c)$
$c_i$ copies, need $O(nW)$	monotone deque per residue class	$O(nW)$
$(1-\epsilon )$ approximation	scale the values, then DP	$O(n^2/\epsilon )$
Few distinct weights	DP over counts
Two constraints (weight and volume)	dp[w][v]	$O(nWV)$

The FPTAS

Round the values down to multiples of $K=\frac{\epsilon v_{\max }}{n}$, then run the value-indexed DP. The rounding loses at most $\epsilon v_{\max }\le \epsilon \mathrm{OPT}$ in total.

double K = eps * maxValue / n;
for (auto& item : items) item.v = (long long)(item.v / K);
// value range is now O(n / eps), so the DP is O(n^2 / eps)

$(1-\epsilon )$-approximate in time polynomial in both $n$ and $1/\epsilon$ — the definition of an FPTAS. Knapsack is the standard example, and it exists precisely because the problem is weakly (not strongly) NP-hard.

Fractional knapsack — the easy cousin

If items may be split, greedy by value density $v_i/w_i$ is optimal: take items in that order, splitting the last.

sort(items.begin(), items.end(), [](auto& a, auto& b) {
    return (double)a.v / a.w > (double)b.v / b.w;         // or a.v * b.w > b.v * a.w
});

Compare with cross-multiplication rather than floating-point division to stay exact. The exchange argument is one line: swapping any two out of density order cannot help.

This is the LP relaxation of 0/1 knapsack, and its value is the standard bound for branch and bound.

Reconstruction

// needs the full 2D table
int cap = W;
for (int i = n - 1; i >= 0; i--)
    if (dp[i + 1][cap] != dp[i][cap]) { chosen.push_back(i); cap -= w[i]; }

With the 1D array this is impossible — that is the cost of the space optimisation. If you need the items, either keep the 2D table or store a take[i][cap] bitset ($nW$ bits, which is often affordable).

Why it is worth knowing

Knapsack is the reference point for the whole DP-versus-NP-hardness discussion:

• it is NP-hard, yet has a simple pseudo-polynomial DP;
• the DP can be inverted when the other dimension is smaller;
• it admits an FPTAS, unlike strongly NP-hard problems;
• its fractional relaxation is greedy-solvable and bounds the integral optimum.

Those four facts together are the standard illustration of what “weakly NP-hard” means in practice.

See also: Knapsack · Subset Sum · Approximation Algorithms