有 2 个限制的算法背包

Question

我一直在做一个项目，我遇到了以下场景:需要从一组 M 中选择 N = 2 个框，同时 M > N 具有最佳权重和但有 2 个限制:

• 我们不能选择相同的盒子颜色
• 不能选择相同的box id

Boxes 排序后权重最高

我用朴素算法选择 (Red1,Blue2)，从最高权重的 Red1 开始，我们无法添加 Blue1，因为我们有相同的 ID 1，也无法添加 Red2，因为我们有权重为10，我们最终的总权重为 11，但如果我们选择 Blue1 和 Red2，我们最终可能会得到 18.9N 可以大于 2。

这是一个 NP-Hard 问题吗？有更好的运行时效率的解决方案吗？

Answer 1

我们可以使用复杂度 O(2^color * 2^id * M * N) 的 DP 解决方案或复杂度 O(M choose N) 的回溯+剪枝

所以这取决于对 M、N、颜色和 id 的约束有多大。