Codacoda
Back to Academy

dynamic programming

0/1 Knapsack

The 0/1 Knapsack problem asks: given a set of items, each with a weight and a value, determine the maximum total value that can be placed in a knapsack of fixed capacity. Each item can either be included or excluded (hence 0/1). A 2D DP table is built where dp[i][w] represents the maximum value achievable using the first i items with capacity w. For each item, we choose the better of skipping it or including it (if it fits).

Use Cases

  • •Resource allocation with budget constraints (project selection, investment portfolios)
  • •Cargo loading optimization for shipping and logistics
  • •Cutting stock problems in manufacturing and material usage

Complexity Analysis

MetricBestAverageWorst
TimeO(nW)O(nW)O(nW)
SpaceO(nW)

Visualization

01234567
0
0
0
0
0
0
0
0
0
w=1,v=1
0
0
0
0
0
0
0
0
w=3,v=4
0
0
0
0
0
0
0
0
w=4,v=5
0
0
0
0
0
0
0
0
w=5,v=7
0
0
0
0
0
0
0
0
Speed:1x
Initialize DP table with zerosStep 1 / 30

Implementation

Output

Click "Run Code" to see output...