我发现在动态规划解决01背包问题时，每个例子中都存在物品的重量（成本）和收益，但从未明确提到需要对物品列表进行排序。然而，在所有这些例子中，它们都按照重量和收益递增的顺序进行排序（在这些例子中，重量越大，利润越高）。因此，我的问题是：当将物品从物品数组/列表添加到矩阵中时，我是否可以以任何顺序添加它们？或者我应该先添加最小重量或者最小利润的物品？因为从多个例子中找不到明确答案，我不确定是巧合还是每次添加最小重量/利润的物品。
你需要为动态规划背包问题排序输入吗？
19
- Tommy K
1
5不需要对背包问题的输入进行排序，如果排序了，那只是为了说明解决方案。您可以尝试以任何顺序输入并运行它，结果应该是相同的。 - Ram Narasimhan
6个回答
10
动态规划解法就是以高效的方式（只需将值保存以供以后参考），选择所有可能性（使用蛮力）。
注意：我们考虑所有子集。无论列表是否排序，子集的总数都相同。因此最终会考虑到所有子集。
注意：我们考虑所有子集。无论列表是否排序，子集的总数都相同。因此最终会考虑到所有子集。
- Shubham Sharma
8
不需要对重量进行排序，因为每一行都给出了在该行重量限制下的最大可能值。最大值将出现在该行的最后一列。
- Shruti Gupta
1
也许你正在寻找自底向上的动态规划解决方案。当您使用自底向上的方法解决问题时，动态规划解决方案具有一个特点。
引用： 第二种方法是自底向上的方法。这种方法通常依赖于某个子问题的“大小”的自然概念，以便解决任何特定的子问题仅取决于解决“更小”的子问题。我们按大小对子问题进行排序，并按大小顺序解决它们，先解决最小的子问题。在解决特定的子问题时，我们已经解决了其解决方案所依赖的所有较小子问题，并保存了它们的解决方案。我们只解决每个子问题一次，并且当我们第一次看到它时，我们已经解决了其先决条件的所有子问题。
来自：算法导论，CORMEN（第3版）
引用： 第二种方法是自底向上的方法。这种方法通常依赖于某个子问题的“大小”的自然概念，以便解决任何特定的子问题仅取决于解决“更小”的子问题。我们按大小对子问题进行排序，并按大小顺序解决它们，先解决最小的子问题。在解决特定的子问题时，我们已经解决了其解决方案所依赖的所有较小子问题，并保存了它们的解决方案。我们只解决每个子问题一次，并且当我们第一次看到它时，我们已经解决了其先决条件的所有子问题。
来自：算法导论，CORMEN（第3版）
- Django
0
在这种情况下，“较小的问题”仅指可供选择的项目数量较少，而不是这些项目的利润或重量。如果给定一个3个项目的列表，则子问题将为2个项目和1个可供选择的项目。
最小的问题首先被硬编码（基本情况），然后在从较小到较大的问题移动的每个阶段，枚举最佳利润，并选择最大值。最后，所有2^n个组合都将被考虑，并且重复的max阶段将推出最大的解决方案。
更改输入顺序或将支配项目放入输入中（例如更高的重量和更低的利润）可能只会更改max()的哪个参数在每个阶段获胜，但最终的max结果将来自相同的项目选择，尽管它们是在算法的不同排序或输入特征的不同阶段选择的。
最小的问题首先被硬编码（基本情况），然后在从较小到较大的问题移动的每个阶段，枚举最佳利润，并选择最大值。最后，所有2^n个组合都将被考虑，并且重复的max阶段将推出最大的解决方案。
更改输入顺序或将支配项目放入输入中（例如更高的重量和更低的利润）可能只会更改max()的哪个参数在每个阶段获胜，但最终的max结果将来自相同的项目选择，尽管它们是在算法的不同排序或输入特征的不同阶段选择的。
- Han Qi
0
我猜，在某些类型的背包问题中可能需要排序。例如，考虑问题"出租车最大收益"。在这里，输入必须按乘客起点排序，否则我们将无法获得最佳结果。
例如，考虑上述问题的以下输入：- 9 [[2,3,1],[2,9,2], [3,6,7],[2,3,6]]
如果您在递归方法中应用典型的背包实现，而不对输入进行排序，则无法获得最佳解决方案。
- Hemanth
0
可以通过一些随机洗牌实验找到答案。 我发现是：按升序排列更好。如果我错了，请纠正我。
要点：https://gist.github.com/whille/39cf7bf8cf5dcf6ac933063735ae54de
问题描述在《算法设计》（ISBN：9780321295354）第6.4章中。 有两种方法：
- 像本章所使用的那样，使用M缓存进行预计算，其中不需要子答案。
- 递归函数，易于理解和测试。我发现Python3.5+的
functools.cache可用于检查需要多少子计算，如我的代码所示：test_random()的升序是currsize中最小的，因此它最有效，并且可以扩展到浮点值。
10个随机权重（1〜100）和200个背包的结果：
[(13.527716157276256, 18.371888775465692), (16.18632175987168, 206.88043031085252), (20.14117982372607, 81.52793937986635), (33.28606671929836, 298.8676699147799), (49.12968642850187, 22.037638580809592), (55.279973594800225, 377.3715225559507), (56.56103181962746, 460.9161412820592), (60.38456825749498, 10.721915577913244), (67.98836121062645, 63.47478755362385), (86.49436333909377, 208.06767811169286)]: reverse: False CacheInfo(hits=0, misses=832, maxsize=None, currsize=832) [(86.49436333909377, 208.06767811169286), (67.98836121062645, 63.47478755362385), (60.38456825749498, 10.721915577913244), (56.56103181962746, 460.9161412820592), (55.279973594800225, 377.3715225559507), (49.12968642850187, 22.037638580809592), (33.28606671929836, 298.8676699147799), (20.14117982372607, 81.52793937986635), (16.18632175987168, 206.88043031085252), (13.527716157276256, 18.371888775465692)]: reverse: True CacheInfo(hits=0, misses=1120, maxsize=None, currsize=1120)method2 注意事项：
- 如果容量很大，所有随机顺序都有相等的 currsize。
- 对于大 N，应避免调用堆栈溢出，因此递归方法应进行转换。通常可以使用两步方法，首先映射子问题依赖关系，然后计算。我稍后会在 gist 中尝试。
- whi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接