Understanding the 0/1 Knapsack Problem and Its Dynamic Programming Solution

The knapsack problem is an interesting and challenging combinatorial optimization task: given a maximum capacity W and N items each with a value and weight, select a subset of items to maximize total value without exceeding the capacity.

Imagine a thief with a limited‑capacity backpack entering a house where each object has a specific weight and value; the thief can either take an entire item or leave it, never a fraction.

Example data: maximum weight W = 10, number of items N = 4, values v[] = {10, 40, 30, 50}, weights w[] = {5, 4, 6, 3}. For this data the optimal value is 90 (items with values 50 and 40) with total weight 7.

The most effective solution uses dynamic programming: compute optimal sub‑solutions for smaller capacities and build up to the full problem.

We build a value matrix V[N][W] (4 rows × 10 columns). The first column (capacity 0) is filled with 0 because no weight can be carried, and the first row (no items) is also 0 because no value can be obtained.

Filling the table proceeds row by row:

Row 1, columns 1‑4 are 0 because the first item weighs 5, which exceeds those capacities.

Row 1, column 5 (capacity 5) receives the value 10 (the first item’s value).

Continuing, for each cell we compare two quantities: the value without the current item (value from the previous row, same column) and the value of the current item plus the best value achievable with the remaining capacity (value from the previous row at column capacity‑itemWeight). The larger of the two is stored.

When evaluating row 3, column 4 (capacity 4), we check whether item 2 (weight 4, value 40) can be taken. Since the previous row’s value at weight 4 is 0, taking item 2 yields a better value of 40.

After all sub‑problems are solved, the final entry V[N][W] gives the optimal value for the full problem (weight 10, four items), which is shown below:

The time complexity of this dynamic programming solution is O(N·W), because the algorithm iterates over N items and W capacities.

A full Java implementation is available in the original article.