假设一个小偷发现自己在一个金库里，里面有几件贵重物品。然而，他意识到他带了一个装满东西的背包 $米$．金库有 $n$Items，其中 $我$重 $S_i$英镑和价值 $v_i$美元。小偷必须选择物品，以便在卖掉物品后尽可能多地赚钱。他创建了一个数组 $最优[我][j]$在哪里 $最优[我][j]$使用物品获得最大价值吗 $我…n - 1$哪个最重 $j$磅。

由于在大学里从未学过计算机科学，小偷很快地为他的问题写下了四个递归关系。他知道只有一个是正确的。帮他找到合适的。

1： $最佳[我][j] = max \{优(i + 1) [j],最优(i + 1) [j-s_i] + v_i \ \ (j \组s_j) \}$2: $\ \最佳[我][j] = max \{优(i + 1) [j + 1] + v_i,最优(i + 1) (j-s_i) \ \ (j \组s_j) \}$3: $\ \最佳[我][j] = max \{最优(张)[j],最优[我][j + s_i] \ \ (j \组s_j) \}$4： $\ \最佳[我][j] = max \{优(i + 1) [j],最优(张)[j + 1 + s_i] \ \ (j \组s_j) \}$