Waste less time on Facebook — follow Brilliant.
×
Computer Science

Dynamic Programming

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\)?

×

Problem Loading...

Note Loading...

Set Loading...