Dynamic Programming Solutions for 0/1, Complete, Unbounded, and Multi‑Knapsack Problems in JavaScript

The article introduces the classic 0/1 knapsack problem, describing how to recover the selected items by tracing back through the DP matrix f(i,j) and presents a full JavaScript implementation that builds the DP table and extracts the optimal item set.

It then discusses space optimisation by observing that each DP row depends only on the previous row, allowing the use of a rolling two‑row array f[2][W+1] to reduce memory from O(nW) to O(W) . The code shows how to alternate between the two rows and update values accordingly.

Further optimisation is achieved with a one‑dimensional DP array for the 0/1 knapsack, iterating the capacity j in reverse to avoid reusing items. The article provides the concise JavaScript function that computes the maximum value using f[j] = Math.max(f[j], f[j‑weights[i]] + values[i]) .

For the complete (unbounded) knapsack, the state transition changes to f(i,j) = max(f(i‑1,j), f(i,j‑weights[i]) + values[i]) . The article shows both a two‑dimensional and a one‑dimensional implementation, emphasizing the forward iteration of capacity to allow unlimited item usage.

The multi‑knapsack (bounded) variant is addressed by converting each item with a limited count into multiple 0/1 items using binary decomposition. This reduces the effective number of items from O(Σ numbers[i]) to O(Σ log numbers[i]) . The code builds new weight and value arrays ws and vs from the binary split and then applies the standard 0/1 DP.

All code snippets are presented within ... blocks, preserving the original JavaScript syntax and comments for clarity.