SG
← Back

0/1 Knapsack

Choose subset maximizing value under weight capacity.

dpknapsackUpdated 2025-09-01

Transition

  • dp[i][w] = max(dp[i-1][w], val+dp[i-1][w-wt])

Optimize

  • 1D array from high to low weight