Lesson 4: Optimization Problems

Knapsack & Interval DP

Solve the ultimate resource allocation puzzles. Master the Knapsack family and Matrix Chain Multiplication using 2D and Interval DP strategies.

80 Minutes

Hard

The Optimization Toolkit

0/1 Knapsack

Items used once

Unbounded

Infinite supply

Fractional

Greedy choice

Matrix Chain

Interval DP

Item Selection Logic

Matrix Split Tree

1. 0/1 Knapsack

The classic "all or nothing" problem. You have a bag with capacity `W` and items with weights and values. Maximize total value without exceeding capacity.

Crucial Choice: At item `i`, do we include it or exclude it?

Space Optimization

You can compress the 2D table into a 1D array if you iterate through weights backwards to avoid using the same item twice.

2D Tabulation Logic

Pseudocode

1function knap01(weights, values, W):
2  n = len(weights)
3  dp = array(n+1, W+1, 0)
4  
5  for i from 1 to n:
6    for w from 0 to W:
7      if w >= weights[i-1]:
8        // Max(Exclude, Include)
9        dp[i][w] = max(
10          dp[i-1][w], 
11          values[i-1] + dp[i-1][w-weights[i-1]]
12        )
13      else:
14        dp[i][w] = dp[i-1][w]
15        
16  return dp[n][W]

Interactive Lab: Knapsack 2D

Adjust the items and capacity. Observe how a small change in weights ripples through the entire DP table.

WeightsValuesCapacity

0/1 Knapsack Table

Speed

i/w	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1 (w=2, v=3)	0	0	0	0	0	0	0	0
2 (w=3, v=4)	0	0	0	0	0	0	0	0
3 (w=4, v=5)	0	0	0	0	0	0	0	0
4 (w=5, v=8)	0	0	0	0	0	0	0	0

Step 1 / 32 (i=1, w=0). Skipped item → carry dp[i-1][w].

Time Complexity

O(N × W)

Where N is number of items and W is total capacity.

Unbounded Variant

In the Unbounded Knapsack, we iterate through weights forwards because we can use the same item multiple times.

2. Matrix Chain (Interval DP)

Instead of deciding "Take vs Skip", we decide "Where to Split?". This is Interval DP. We compute solutions for small sub-intervals and combine them.

The Split Core

split_cost = dp[i][k] + dp[k+1][j] + cost_to_combine

Common patterns: Matrix Chain, Optimal Binary Search Tree, Burst Balloons.

O(n^3) Matrix Chain Logic

Pseudocode

1function matrixChain(p):
2  n = len(p) - 1
3  dp = array(n, n, 0)
4  
5  for len from 2 to n: // Interval length
6    for i from 1 to n - len + 1:
7      j = i + len - 1
8      dp[i][j] = INF
9      
10      for k from i to j-1: // Split points
11        cost = dp[i][k] + dp[k+1][j] 
12               + p[i-1] * p[k] * p[j]
13        dp[i][j] = min(dp[i][j], cost)
14        
15  return dp[1][n]

Strings & Sequences Finish Module: Summary

1. 0/1 Knapsack

Space Optimization

You can compress the 2D table into a 1D array if you iterate through weights backwards to avoid using the same item twice.

1function knap01(weights, values, W): 2 n = len(weights) 3 dp = array(n+1, W+1, 0) 4 5 for i from 1 to n: 6 for w from 0 to W: 7 if w >= weights[i-1]: 8 // Max(Exclude, Include) 9 dp[i][w] = max( 10 dp[i-1][w], 11 values[i-1] + dp[i-1][w-weights[i-1]] 12 ) 13 else: 14 dp[i][w] = dp[i-1][w] 15 16 return dp[n][W]

i/w

1 (w=2, v=3)

2 (w=3, v=4)

3 (w=4, v=5)

4 (w=5, v=8)

1function matrixChain(p): 2 n = len(p) - 1 3 dp = array(n, n, 0) 4 5 for len from 2 to n: // Interval length 6 for i from 1 to n - len + 1: 7 j = i + len - 1 8 dp[i][j] = INF 9 10 for k from i to j-1: // Split points 11 cost = dp[i][k] + dp[k+1][j] 12 + p[i-1] * p[k] * p[j] 13 dp[i][j] = min(dp[i][j], cost) 14 15 return dp[1][n]