DevJourney · code I wrote while learning

README.md

1.2 KB

0-1 Knapsack (Dynamic Programming)

Problem

  • Given n items, each with weight w[i] and value v[i], and a knapsack capacity W, select a subset of items (each at most once) to maximize total value without exceeding capacity.

Key idea

  • Use DP where dp[i][c] is the maximum value achievable using the first i items with capacity c. The decision for item i is to take it (if it fits) or skip it.

Recurrence

  • dp[0][*] = 0
  • For i from 1..n and capacity c from 0..W:
    • if w[i] > c: dp[i][c] = dp[i-1][c]
    • else: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i])

Space optimization

  • You can reduce space to a 1D array dp[c] iterating items and capacities in descending order (to avoid reuse within the same item).

Complexity

  • Time: O(n * W)
  • Space: O(n * W) or O(W) with the optimized 1D DP (but reconstructing chosen items needs extra bookkeeping).

Worked example

n = 4, W = 7
weights = [1,3,4,5]
values  = [1,4,5,7]
  • Optimal: items with weights 3 and 4 (value 4 + 5 = 9) fit exactly into capacity 7.

Notes

  • DP is pseudo-polynomial because it depends on W. For large W consider approximation or meet-in-the-middle for moderate n.

Code: main.cpp — implements the DP and prints maximum value and chosen items.