假设一个小偷发现自己在一个藏有几件贵重物品的保险库中。然而，他意识到他带来了一个容量很大的背包 $米$．金库有 $n$Items，其中item $我$重 $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) \}$