Return 多项选择背包变化的 N 个最优选择
Return N Optimal Choices for Multiple Choice Knapsack Variation
问题
我正在尝试 return N 个最佳答案（对于确切的数字，我想要 250 个）。根据我对动态规划的理解，它将 return 一个最佳答案。所以我相信我必须使用回溯才能生成 N 个最佳答案。
对于背包变体问题，我有一个物体组合不应该通过的最大重量。我有 4 组对象，必须从每组中选择一个 来给出 最高值 不超过重量限制。集合中的每个对象都有一个值和一个权重。
这些集合有 164、201、90 和 104 个对象，这意味着有 308,543,040 种变化可供尝试。我实施了一个蛮力算法，但它需要很长时间。
优化尝试
到目前为止，我的优化尝试是通过增加权重排序来预处理输入集。 （最低的优先）。在添加每个对象时，如果约束权重大于对象的组合权重，那么我可以跳过该集合的其余部分，因为所有其他选项都将无效。这可以是 运行 在递归函数的任何级别。
我还有一个最小堆，用于存储我找到的最大值。如果四个对象的组合小于堆顶，则不添加。否则，pushpop 到堆。我不确定我是否可以使用它来进一步优化回溯，因为它需要选择所有四个对象。它更多地用作验证而不是提高速度。
问题
- 我可以用回溯做任何其他优化来加快找到 N 个最佳答案的过程吗？我已经用尽了优化，应该只使用多线程吗？
- 是否可以使用动态规划？如何将动态规划修改为 return N 个最优选择？
- 还有其他算法需要研究吗？
由于必须从每个集合中恰好挑选一个项目，您可以尝试这种优化：
- 设集合为
A,B,C,D。
- 创建集合
A,B 和集合 C,D 中项目的所有组合。这将具有 O(n^2) 的复杂性，假设列表的长度为 n。现在让组合列表为 X 和 Y。
- 根据权重对
X 和 Y 进行排序。您可以使用诸如累积数组之类的东西来跟踪给定权重下具有最大可能值的组合。 （其他数据结构也可能用于相同的任务，这只是一个强调基本思想的建议）。
- 创建一个最大堆来存储具有最大值的组合
- 对于
X中的每个组合，在其权重为<= target weight - X_combination_weight的约束下，选择Y中具有最高值的组合。根据这个组合的值，将其插入到最大堆中。
问题
我正在尝试 return N 个最佳答案（对于确切的数字，我想要 250 个）。根据我对动态规划的理解，它将 return 一个最佳答案。所以我相信我必须使用回溯才能生成 N 个最佳答案。
对于背包变体问题，我有一个物体组合不应该通过的最大重量。我有 4 组对象，必须从每组中选择一个 来给出 最高值 不超过重量限制。集合中的每个对象都有一个值和一个权重。
这些集合有 164、201、90 和 104 个对象，这意味着有 308,543,040 种变化可供尝试。我实施了一个蛮力算法，但它需要很长时间。
优化尝试
到目前为止，我的优化尝试是通过增加权重排序来预处理输入集。 （最低的优先）。在添加每个对象时，如果约束权重大于对象的组合权重，那么我可以跳过该集合的其余部分，因为所有其他选项都将无效。这可以是 运行 在递归函数的任何级别。
我还有一个最小堆，用于存储我找到的最大值。如果四个对象的组合小于堆顶，则不添加。否则，pushpop 到堆。我不确定我是否可以使用它来进一步优化回溯，因为它需要选择所有四个对象。它更多地用作验证而不是提高速度。
问题
- 我可以用回溯做任何其他优化来加快找到 N 个最佳答案的过程吗？我已经用尽了优化，应该只使用多线程吗？
- 是否可以使用动态规划？如何将动态规划修改为 return N 个最优选择？
- 还有其他算法需要研究吗？
由于必须从每个集合中恰好挑选一个项目，您可以尝试这种优化：
- 设集合为
A,B,C,D。 - 创建集合
A,B和集合C,D中项目的所有组合。这将具有O(n^2)的复杂性，假设列表的长度为n。现在让组合列表为X和Y。 - 根据权重对
X和Y进行排序。您可以使用诸如累积数组之类的东西来跟踪给定权重下具有最大可能值的组合。 （其他数据结构也可能用于相同的任务，这只是一个强调基本思想的建议）。 - 创建一个最大堆来存储具有最大值的组合
- 对于
X中的每个组合，在其权重为<= target weight - X_combination_weight的约束下，选择Y中具有最高值的组合。根据这个组合的值，将其插入到最大堆中。