algorithm - 返回多项选择背包变化的 N 个最优选择

Question

问题

我正在尝试返回N 个最佳答案(对于我想要的确切数字 250)。根据我对动态规划的理解，它将返回一个最佳答案。所以我相信我必须使用回溯来生成 N 个最佳答案。

对于背包变体问题，我有一个物体组合不应超过的最大重量。我有4 组对象，并且必须从每组中选择一个才能给出最高值而不超过重量限制。集合中的每个对象都有一个值和一个权重。

这些套装有 164、201、90 和 104 个对象，这意味着有 308,543,040 种变化可供尝试。我实现了一个强力算法，但它需要很长时间。

尝试优化

到目前为止，我的优化尝试是通过增加权重排序来预处理输入集。 (最低的优先)。添加每个对象时，如果约束权重大于对象的组合权重，那么我可以跳过该组的其余部分，因为所有其他选项都无效。这可以在递归函数的任何级别运行。

我还有一个最小堆，用于存储我找到的最大值。如果四个对象的组合小于堆顶，则不会添加。否则，将 pop 插入堆。我不确定是否可以使用它来进一步优化回溯，因为它需要选择所有四个对象。它更多地用作验证而不是提高速度。

问题

• 我还可以通过回溯进行其他优化，以加快寻找 N 个最佳答案的过程吗？我是否已经用尽优化，应该只使用多个线程？
• 可以使用动态规划吗？如何修改动态规划以返回 N 个最优选择？
• 还有其他值得研究的算法吗？

Answer 1

由于必须从每组中挑选一个项目，因此您可以尝试以下优化:

1. 设集合为 A,B,C,D .
2. 创建集合中项目的所有组合 A,B一起并设置C,D一起。这将有 O(n^2)复杂性，假设列表有长度 n 。令组合列表为 X和Y现在。
3. 排序 X和Y基于重量。您可以使用累积数组之类的东西来跟踪给定权重下最大可能值的组合。 (其他数据结构也可能用于相同的任务，这只是一个强调基本思想的建议)。
4. 创建一个最大堆来存储具有最大值的组合
5. 对于 X 中的每个组合，选择 Y 中的组合在其权重为 <= target weight - X_combination_weight 的约束下具有最高值。根据此组合的值，将其插入到最大堆中。