把最有价值的东西放在盒子里
Put the most valuable items in a box
我正在做如下编程练习：
有一个盒子和一个物品清单。
盒子有固定的尺寸。每件商品都有自己的尺码和价格。
如果物品的总和小于盒子的尺寸，我们可以在盒子里放任意数量的物品。 (每件物品只能放一次)
找出价格最高的可以放入箱子的物品组合。
box: size = 10
| item | size | price |
| ---- | ---- | ----- |
| 1 | 8 | 4 |
| 2 | 10 | 5 |
| 3 | 1 | 2 |
在这种情况下，答案将是 6，因为选择了项目 1 和 3，价格 4 + 2 = 6（尺码总和为 8，小于 10）
我的做法是通过回溯找到所有可能的组合，记录最高价，但我不确定如果列表中的项目数量巨大，是否足够高效。
有没有更有效的方法？
这正是0/1 knapsack problem。确实尝试所有组合将解决问题，但如果超过 50 个项目，则需要很长时间。
问题是NP-完全的，但是可以伪多项式求解。也就是如果box的总尺寸比较小，可以高效的解决。
是的，有一种更有效的方法！
动态编程 - 自下而上
方法： 不是通过评估所有可能的子集来强制解决方案，而是可以针对每个项目在每个权重下迭代解决问题。举个例子：
假设有四个项目 i[1,2,3,4]，相关权重 w[5,3,4,2]，值 v[60,50,70,30] 和最大权重 w = 5。
我们现在来构建一个二维值数组，在选择某个物品某个重量时保存最大值，V[i][w]。
填充数组的算法是：
V[i][w] = max(V[i-1, w], V[i-1, w - w_i] + v_i) OTHERWISE V[i-1, w]
这是做什么的？ :
对于每个重量的每个项目，我们首先看是否可以在不超过重量限制的情况下选择该项目。如果不是，我们将采用该重量的上述项目的值（如果也无法选择该项目，则为 0）。
如果我们可以选择项目，有趣的事情就会发生。如果是这样，如果选择的项目大于选择上面的项目的值，我们选择当前项目代替：
(So if V[i-1, w] < V[i-1, w - w_i] + v_i)
对所有 n 件物品和 w 件重量都这样做，您将获得尽可能高的价值。
在上述示例中执行算法时，这将是矩阵：
w
0
1
2
3
4
5
Item 1
0
0
0
0
0
60
Item 2
0
0
0
50
50
60
Item 3
0
0
0
50
70
70
Item 4
0
0
30
50
70
80
现在要解决背包问题，我们看一下为 w = 5 选择项目的值。我们看到选择项目 4 产生了最大值。我们还可以看到该值的来源。如果我们选择第 4 项，从权重中减去 2，我们将落在 w = 3 的列中。然后我们上升一行，因为我们已经选择了第 4 项并且不能再次选择它。然后我们查看了第 3 项，但是如果我们从 w = 3 中减去 w_3，我们得到 -1，所以我们知道这一列中的值是从上面的行继承的，所以我们查看第 2 行. w = 3 减去w_2 得到0，所以我们知道这个row/column 中的值来自于选择项目2。这最终告诉我们价值80 是通过选择项目2 然后选择项目4 得到的.
与 O(2 ^ N) 相比，运行 的复杂度为 O(N * W)蛮力方法。
我正在做如下编程练习：
有一个盒子和一个物品清单。
盒子有固定的尺寸。每件商品都有自己的尺码和价格。
如果物品的总和小于盒子的尺寸，我们可以在盒子里放任意数量的物品。 (每件物品只能放一次)
找出价格最高的可以放入箱子的物品组合。
box: size = 10
| item | size | price |
| ---- | ---- | ----- |
| 1 | 8 | 4 |
| 2 | 10 | 5 |
| 3 | 1 | 2 |
在这种情况下，答案将是 6，因为选择了项目 1 和 3，价格 4 + 2 = 6（尺码总和为 8，小于 10）
我的做法是通过回溯找到所有可能的组合，记录最高价，但我不确定如果列表中的项目数量巨大，是否足够高效。
有没有更有效的方法？
这正是0/1 knapsack problem。确实尝试所有组合将解决问题，但如果超过 50 个项目，则需要很长时间。
问题是NP-完全的，但是可以伪多项式求解。也就是如果box的总尺寸比较小，可以高效的解决。
是的，有一种更有效的方法！
动态编程 - 自下而上
方法： 不是通过评估所有可能的子集来强制解决方案，而是可以针对每个项目在每个权重下迭代解决问题。举个例子：
假设有四个项目 i[1,2,3,4]，相关权重 w[5,3,4,2]，值 v[60,50,70,30] 和最大权重 w = 5。
我们现在来构建一个二维值数组，在选择某个物品某个重量时保存最大值，V[i][w]。
填充数组的算法是：
V[i][w] = max(V[i-1, w], V[i-1, w - w_i] + v_i) OTHERWISE V[i-1, w]
这是做什么的？ :
对于每个重量的每个项目，我们首先看是否可以在不超过重量限制的情况下选择该项目。如果不是，我们将采用该重量的上述项目的值（如果也无法选择该项目，则为 0）。
如果我们可以选择项目，有趣的事情就会发生。如果是这样，如果选择的项目大于选择上面的项目的值，我们选择当前项目代替：
(So if V[i-1, w] < V[i-1, w - w_i] + v_i)
对所有 n 件物品和 w 件重量都这样做，您将获得尽可能高的价值。 在上述示例中执行算法时，这将是矩阵：
| w | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| Item 1 | 0 | 0 | 0 | 0 | 0 | 60 |
| Item 2 | 0 | 0 | 0 | 50 | 50 | 60 |
| Item 3 | 0 | 0 | 0 | 50 | 70 | 70 |
| Item 4 | 0 | 0 | 30 | 50 | 70 | 80 |
现在要解决背包问题，我们看一下为 w = 5 选择项目的值。我们看到选择项目 4 产生了最大值。我们还可以看到该值的来源。如果我们选择第 4 项，从权重中减去 2，我们将落在 w = 3 的列中。然后我们上升一行，因为我们已经选择了第 4 项并且不能再次选择它。然后我们查看了第 3 项，但是如果我们从 w = 3 中减去 w_3，我们得到 -1，所以我们知道这一列中的值是从上面的行继承的，所以我们查看第 2 行. w = 3 减去w_2 得到0，所以我们知道这个row/column 中的值来自于选择项目2。这最终告诉我们价值80 是通过选择项目2 然后选择项目4 得到的.
与 O(2 ^ N) 相比，运行 的复杂度为 O(N * W)蛮力方法。