Backward traversal is the fix for a subtle bug: when you update dp[w] going forward, the item i you're processing could get counted again in the same iteration. Going backward, dp[w - weight[i]] is guaranteed to still hold the value from item i-1, so you never double-count.

The 1D optimization works because dp[w] only ever reads from dp[w - weight[i]]. After you update dp[w] for item i, you never need the old dp[w] again in the same item's iteration—it's consumed. Backward traversal ensures that when you read dp[w - weight[i]], you haven't overwritten it yet with item i's contribution. This collapses the 2D table to a single row without losing correctness.

Fractional knapsack has the greedy-choice property: picking the item with the highest value-to-weight ratio always leads to an optimal solution. You can cut it, so filling your capacity with the best ratio items first never backfires. 0/1 knapsack doesn't have this property—grabbing a high-ratio item might prevent you from taking several medium-ratio items that together are worth more. This missing optimal substructure is exactly what makes 0/1 NP-hard.

Multi-dimensional knapsack adds a second constraint (volume, cost, time—whatever matters for your problem). You expand the DP table to track both: dp[w][v] holds the max value achievable with weight w and volume v. The transition checks both limits before adding an item. Complexity multiplies: O(n × maxWeight × maxVolume). This shows up in container loading, vehicle routing with fuel constraints, and portfolio selection with transaction costs.

Split the items in half—call them left and right. Enumerate every subset sum for each half (2^(n/2) each, which is manageable up to about n=40). Then combine them: for each subset sum from the left, find the best matching sum from the right that fits within the capacity. This turns O(2^n) brute force into O(2^(n/2)), which is the difference between waiting forever and getting an answer before your interview ends.

Bounded knapsack specifies how many copies of each item you can take (e.g., item i has quantity limit m[i]). The state transition adds a third dimension: dp[i][w] = max(dp[i-1][w], dp[i-1][w - k*weight[i]] + k*value[i]) for k = 1 to min(m[i], w/weight[i]). A common optimization uses binary decomposition: split each item into powers-of-two bundles (1, 2, 4, ..., remainder) and treat each bundle as a separate 0/1 item, reducing bounded to O(n log max_quantity) items.

Subset sum is a special case of 0/1 knapsack where all values equal weights (or values are the targets themselves). The recurrence dp[w] = dp[w] or dp[w - num] mirrors knapsack with unit values. Conversely, any 0/1 knapsack can be reduced to subset sum by treating (value - weight) pairs as numbers and looking for a target sum, though the transformation loses the optimization objective. Subset sum being NP-complete confirms 0/1 knapsack is NP-hard.

The 2D table dp[i][w] is necessary when you need to reconstruct which items were selected. The space-optimized version discards which items contributed to each state. Also, the 2D version can be easier to debug since each row represents a clear "first i items" boundary. Use 1D only when you need the final maximum value and don't care about the actual selection.

Base cases: dp[0][w] = 0 (zero items can produce zero value) and dp[i][0] = 0 (zero capacity holds zero value). These anchor the recurrence. All other cells start at 0 because we're maximizing and the minimum achievable value is 0 (no items selected). Incorrect initialization—like starting at negative infinity—would corrupt the recurrence. The base case also reveals why negative weights require special handling: they break the natural ordering of capacity.

Use a 2D DP table where dp[i][v] = minimum weight needed to achieve at least value v using first i items. Traverse values in ascending order and stop when no feasible solution exists (weight exceeds capacity). Alternatively, use Pareto optimality: track all non-dominated pairs (value, weight) and prune any solution strictly worse in both dimensions. This produces a Pareto frontier rather than a single solution.

Tabulation builds the DP table iteratively from smaller subproblems up to the full solution—fast but processes all states even if unused. Memoization (top-down) recursively computes only states actually reached, lazily filling the table. Memoization avoids wasted work on sparse state spaces but has recursion overhead. For knapsack, tabulation is usually faster due to no function call overhead; memoization shines when the reachable state space is much smaller than the full n x W grid.

Use arbitrary-precision integers (Python's int handles this natively). In languages like C++ or Java, use BigInteger or BigDecimal. Alternatively, normalize values: if weights are large but limited in range, use dictionary-based sparse representation (hash maps instead of arrays) to store only reachable states. A third approach: scale weights to smaller units or use modular arithmetic if the problem structure permits.

No greedy algorithm guarantees the optimal 0/1 knapsack solution. A common heuristic sorts by value-to-weight ratio (v_i/w_i) and picks items until capacity is full—it runs in O(n log n) but can be arbitrarily far from optimal. Acceptable when: (1) speed matters more than precision, (2) items are small and uniformly distributed, (3) you need a quick bound for branch-and-bound. The greedy solution also serves as a warm start for iterative improvement.

Negative weights break standard DP assumptions because adding a negative weight could increase remaining capacity, creating cycles. Solutions: (1) Shift all weights to positive by adding a constant, then adjust capacity; (2) Use unconstrained DP with a hash map keyed by actual weight sum, tracking max value for each reachable weight; (3) If only some weights are negative, treat them separately—negative-weight items should always be taken if valuable (unbounded effect) and require special handling in the recurrence. The problem becomes strongly NP-hard even with a single negative weight.

Branch and bound explores the item decision tree but prunes branches that cannot beat the current best solution. A bound is computed using the fractional knapsack relaxation (upper bound = current value + remaining capacity × best value-per-weight among undecided items). The algorithm: (1) Sort items by density descending; (2) Recursively decide to include/exclude each item; (3) Bound: if fractional upper bound ≤ best known integer solution, prune. For n=30-50 items this can solve problems that brute force O(2^n) cannot, though worst case is still exponential.

Multiple knapsack assigns each item to at most one of K knapsacks with individual capacities W_1...W_k. The straightforward approach adds a dimension: dp[i][w1][w2]...[wk]—exponential in K, quickly intractable. Practical approaches: (1) Merge knapsacks into one super-capacity if items are fungible; (2) Use integer linear programming (ILP) solvers for exact solutions; (3) Apply greedy decomposition—assign items to the knapsack with most remaining capacity—then locally optimize with exchanges between knapsacks.

O(nW) is not polynomial in the input size because W is represented in binary, requiring log(W) bits. A truly polynomial algorithm would be O(n^c) where c is constant. For W = 2^100 (astronomical), even n=1 gives 2^100 operations. This matters for cryptography (large key spaces) and any problem where capacity grows exponentially with input encoding. Mitigation: approximation schemes (PTAS), integer linear programming, or heuristic methods when W is large relative to n.

Dynamic capacity arises in problems like budget cycles or cargo with refueling stops. Two approaches: (1) Expand the state to include time/capacity dimension: dp[i][w][t] where t is the time step and capacity varies deterministically (e.g., decays or resets); (2) Treat each time period as a separate knapsack subproblem and use the solution as input for the next period. If capacity changes stochastically, use Markov decision process (MDP) formulation with value iteration. The complexity grows multiplicatively with time steps.

Both guarantee a (1-ε) optimal solution. PTAS runs in O(n^(1/ε))—polynomial in n but exponential in 1/ε. FPTAS runs in O(n^3 / ε) or O(n^2 / ε)—truly polynomial in both n and 1/ε. The FPTAS for knapsack works by scaling values: divide all values by a factor that rounds them to O(n/ε) distinct levels, then solve the rounded instance with DP. The rounding introduces at most (1-ε) error. FPTAS is preferred when you need a provable bound with scalable precision.

Item dependencies form a constraint graph. Solutions: (1) If dependencies form a DAG, perform topological sort and use grouped DP where each strongly connected component is collapsed into a "composite item" with all valid internal combinations precomputed; (2) Add an "include flag" for each dependency pair: treat (A, B) as a combined item with weight = w_A + w_B and value = v_A + v_B; (3) Use the inclusion-exclusion principle for OR constraints where taking B requires either A or C (A ∪ C). For complex dependency graphs, consider ILP formulation which natively expresses logical constraints.