the FPTAS for knapsack

The 0/1 knapsack problem: you have items each with a weight and a value, a sack of fixed capacity, and you want the most valuable subset that fits. It is NP-hard, yet it has a fully polynomial-time approximation scheme — you can get within (1 + epsilon) of the best possible value, for any epsilon, in time polynomial in both n and 1/epsilon. It is the cleanest concrete example of how 'rounding and scaling' a dynamic program turns NP-hardness into arbitrarily-good approximation.

The construction rests on a key fact about knapsack's exact DP. There are two ways to fill the DP table: one indexed by weight, one indexed by VALUE. The value-indexed DP computes, for each achievable total value, the minimum weight needed to reach it, and its running time is polynomial in n and in the largest item value V — fast if values are small, but V can be huge, so this is only pseudo-polynomial. Here is the trick that tames V. Pick a scaling factor K = (epsilon * V_max) / n, and replace each item's value v_i with the rounded-down scaled value floor(v_i / K). The values are now small integers (the largest is about n / epsilon), so the value-indexed DP runs in time polynomial in n and 1/epsilon. Solve knapsack exactly on these rounded values, and output that subset. Why is it near-optimal? Each item's value was reduced by less than K when we rounded down, and the optimal solution holds at most n items, so the total value lost is less than n * K = epsilon * V_max. Since the true optimum is at least V_max (the single most valuable item fits, assuming each item fits alone), the loss is at most an epsilon fraction of OPT. So the rounded solution's true value is at least (1 - epsilon) * OPT.

This is the canonical FPTAS and the template generalizes: scale the numbers down to make a pseudo-polynomial DP fast, and bound the rounding error against OPT. The honesty here is in what the scaling buys and costs. Rounding values (not weights) is essential — you may never violate the capacity, so weights stay exact while only values are coarsened. The accuracy knob epsilon trades directly against running time: smaller epsilon means a larger K-denominator, more distinct values, a bigger DP table, all polynomially. And it is no contradiction with knapsack being NP-hard: an FPTAS gives near-optimal in polynomial time, never the exact optimum, so P versus NP is untouched.