###### Waste less time on Facebook — follow Brilliant.
×
Back to all chapters

# Dynamic Programming

You don't want to repeat yourself when trying to be efficient. Dynamic programming is the art of keeping track of results you've already computed that are useful in later computations.

# Backpack Problem

Give a set of eight items with a corresponding weight and value:

What are the items used with the maximum possible value we can get, knowing that the knapsack's weight limit is $$12$$?

Suppose a thief finds himself in a vault containing several valuables. He realizes howeber that he brough a knapsack of capacity $$M$$. The vault has $$n$$ items, item $$i$$ weighing $$S_i$$ pounds and worth $$v_i$$ dollars. The thief must choose the items so that that he’ll make as much money as possible after selling the items. . He creates an array $$optimal[i][j]$$ where $$optimal[i][j]$$ is the maximum value obtained by using items $$i ... n-1$$ which weigh at most $$j$$ pounds.

Having never been in computer-science in college, the thief quickly scribbles four recurrence relationships for his problem. He knows only one is right. Help him find the right one.

1: $optimal[i][j] = max \{ optimal[i+1][j] , optimal[i+1][j-s_i] + v_i \ \ ( j \geq s_j ) \}$ 2: $\ \ optimal[i][j] = max \{ optimal[i+1][j+1] + v_i , optimal[i+1][j-s_i] \ \ ( j \geq s_j ) \}$ 3: $\ \ optimal[i][j] = max \{ optimal[i-1][j] , optimal[i][j+s_i] \ \ ( j \geq s_j ) \}$ 4: $\ \ optimal[i][j] = max \{ optimal[i+1][j] , optimal[i-1][j+1+s_i] \ \ ( j \geq s_j ) \}$

Give a set of eight items with a corresponding weight and value:

You want to carry as many items as you can without exceeding your knapsack's weight limit. What's the maximum possible value you can get knowing that the knapsack's weight limit is $$12$$?

×