Quantitative Finance

Computer Science Concepts

Backpack Problem

     

Suppose a thief finds himself in a vault containing several valuables. He realizes however that he brough a knapsack of capacity MM. The vault has nn items, where item ii weighs SiS_i pounds and is worth viv_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]optimal[i][j] where optimal[i][j]optimal[i][j] is the maximum value obtained by using items i...n1i ... n-1 which weigh at most jj 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][jsi]+vi  (jsj)}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]+vi,optimal[i+1][jsi]  (jsj)}\ \ 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[i1][j],optimal[i][j+si]  (jsj)}\ \ 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[i1][j+1+si]  (jsj)}\ \ 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 1212?

A table of eight items with their corresponding weights and values is given below.

Suppose that the knapsack's weight limit is 1212, and our goal is to store the greatest possible total value inside of it. If we can only use items from the table, and we only have one of each item, what combination of items can be stored inside the bag to achieve our goal?

×

Problem Loading...

Note Loading...

Set Loading...