In this section we will discuss the dynamic programming algorithm to solve the 0-1 Knapsack Problem.
The 0-1 Knapsack problem is a classic use of Dynamic Programming (DP): a technique that breaks a problem into smaller, overlapping subproblems and stores their results to avoid recomputation. A naive recursive solution considers each item in turn and branches on two choices: include it or exclude it. This yields a binary recursion tree with up to \(2^n\) leaves and repeats many subcases. For example, different decision paths may both end up considering the same situation— say, "items 4 through 6 with 10 units of capacity left"—even though they reached it in different ways. DP recognizes these repeated subproblems and reuses their results, turning the exponential search into a polynomial-time table computation.
The key idea is to build the solution gradually, adding one item at a time. Suppose we already know the best way to fill a knapsack of any smaller capacity using the first \(i-1\) items. When we now consider item \(i\), there are two possibilities: take it (if it fits) or do not take it. If we skip it, the total value remains whatever was best for the first \(i-1\) items and the same capacity. If we take it, we gain its value \(v_i\) but reduce our remaining capacity by \(w_i\), so we must add \(v_i\) to the best value achievable with capacity \(w - w_i\) from the previous items.
This reasoning leads to a subproblem definition \(V(i, w)\): the maximum value achievable using items \(0\) through \(i\) with total capacity \(w\). We fill the table one item at a time, beginning with item 0.
Putting it all together, we get the following recursive formula to compute the optimal solution for the first \(i\) items and capacity \(w\):
\(V(i, w) = \begin{cases} 0, & \text{if } i = 0 \text{ and } w_0 > w,\\[6pt] v_0, & \text{if } i = 0 \text{ and } w_0 \le w,\\[6pt] V(i-1, w), & \text{if } w_i > w,\\[6pt] \max\big(V(i-1, w),\ v_i + V(i-1, w - w_i)\big), & \text{otherwise.} \end{cases}\)
A bottom-up DP implementation fills a table of size \(n \times (W+1)\), where each cell \(V(i, w)\) represents the best total value achievable using items \(0\) through \(i\) with capacity \(w\). The final entry \(V(n-1, W)\) gives the maximum total value.
After the table is filled, \(V(n-1, W)\) gives the best total value. To recover items, trace back from \((n-1, W)\). At each state \((i, w)\), compare \(V(i, w)\) with \(V(i-1, w)\):
Stop when \(i = 0\) or \(w = 0\). For \(i = 0\), include item 0 iff \(V(0, w) = v_0\) (i.e., it fits), then finish.
If this still feels abstract, the demonstration below will make the process more concrete. It shows both how the table of values is filled and how the optimal solution is then reconstructed by tracing back through the entries. Step through it slowly to see how each decision affects later values, and how the final path reveals which items make up the best combination.
The following implementations use a bottom-up dynamic programming approach to compute the value of the optimal solution, but not the items. Extending the code to include the list of items is left to the reader.
A few details are worth noting:
public static int knapsack(int[] values, int[] weights, int W) {
int n = values.length;
int[][] K = new int[n][W + 1];
// Row 0 initialization
for (int c = 0; c <= W; c++) {
K[0][c] = (weights[0] <= c) ? values[0] : 0;
}
// Fill remaining rows
for (int i = 1; i < n; i++) {
for (int c = 0; c <= W; c++) {
if (weights[i] <= c) {
K[i][c] = Math.max(K[i - 1][c], values[i] + K[i - 1][c - weights[i]]);
} else {
K[i][c] = K[i - 1][c];
}
}
}
return K[n - 1][W];
}#include <algorithm>
int knapsack(int values[], int weights[], int n, int W) {
int K[n][W + 1];
// Row 0 initialization
for (int c = 0; c <= W; c++) {
K[0][c] = (weights[0] <= c) ? values[0] : 0;
}
// Fill remaining rows
for (int i = 1; i < n; i++) {
for (int c = 0; c <= W; c++) {
if (weights[i] <= c) {
K[i][c] = max(K[i - 1][c], values[i] + K[i - 1][c - weights[i]]);
} else {
K[i][c] = K[i - 1][c];
}
}
}
return K[n - 1][W];
}def knapsack(values, weights, W):
n = len(values)
if n == 0 or W <= 0:
return 0
K = [[0] * (W + 1) for _ in range(n)]
# Row 0 initialization
for c in range(W + 1):
K[0][c] = values[0] if weights[0] <= c else 0
# Fill remaining rows
for i in range(1, n):
for c in range(W + 1):
if weights[i] <= c:
K[i][c] = max(K[i - 1][c], values[i] + K[i - 1][c - weights[i]])
else:
K[i][c] = K[i - 1][c]
return K[n - 1][W]Time Complexity. The table has \(n\) rows (items \(0..n-1\)) and \(W+1\) columns (capacities \(0..W\)). Each cell \(V(i, w)\) is computed in \(O(1)\) time from at most two earlier cells. Therefore the total time is \(O(nW)\).
Pseudo-polynomial note. The algorithm is considered pseudo-polynomial because its running time grows with the numeric value of \(W\) rather than the size of its representation. In practice, it runs efficiently when \(W\) is moderate but can become impractical when \(W\) is very large (for example, \(W = 2^n).\) The subtle point is that while the input size is proportional to \(\log W\)—the number of bits needed to write down \(W\)—the algorithm's time depends directly on \(W\) itself. Thus, even though the algorithm is polynomial in \(n\) and \(W\), it is not polynomial in the total input size. Since 0-1 Knapsack is NP-hard, this limitation is expected: a truly polynomial-time algorithm is unlikely to exist.
Pseudo-polynomial note. The running time depends on the numeric capacity \(W\), not on the bit-length \(\log W\). This algorithm is considered pseudo-polynomial time: it is efficient when \(W\) is moderate, but can be large when \(W\) is large (e.g if \(W=2^n\)). Since 0-1 Knapsack is NP-hard, it is not surprising that this algorithm is not polynomial time.
Space Complexity. The 2D table stores \(n(W+1)\) integers, so space is \(O(nW)\) beyond the input arrays. If we only need the optimal value (not reconstruction), we can compress to a 1D array of size \(W+1\), updating capacities in descending order, for \(O(W)\) extra space.
Reconstruction cost. If we keep the full table, recovering one optimal set of items by tracing back takes \(O(n)\) time and no extra asymptotic space (just an output list).