约束和算法

Question

我正在尝试解决的问题涉及一张项目表：

Item | x | y | z | ... | n
================
A    | 2 | 3 | 1
B    | 6 | 6 | 8
C    | 9 | 2 | 1
D    | 1 | 5 | 7
.
.
.
w

{x, y, z, ..., n} 的值可以是任意的，行数和列数也可以是任意的。

当您将项目组合在一起时，会有约束条件，使得它们的总和为：

1. 7 <= sum(x) <= 10
2. 10 <= sum(y) <= 15
3. 8 <= sum(z) <= 10}

并且。

4. The number of items is 2 <= numItems <= 10

一个可能的解决方案是：A + B（x = 8，y = 9，z = 9）。

目标是找到所有满足此条件的可能组合。如果这需要太长时间，则只需找到一些非常小的子集即可。

我的问题是是否有任何良好的算法来解决这个问题？这不是作业问题或其他什么，而是我个人项目的一部分。我一直在尝试想出一个好的解决方法，但似乎总是得到非常低效的解决方案。希望我错过了什么。

- Chris Kdon

---

8 <= sum(x) <= 10} 应该改为 8 <= sum(z) <= 10}，而且项目只固定为 A、B、C、D 吗？ - Kunukn

你是想找到满足约束条件的任何组合吗？还是目标是找到最好的满足条件的组合？（对于某种定义的最佳） - cyon

最终我想要满足所有组合。但是我可能需要只使用找到的第一个组合。numItems范围的限制也是可变的。 - Chris Kdon

@Kunukn修复了，谢谢。不，项目数量是不固定的。我会更新问题以反映这一点。 - Chris Kdon

请注意，这个问题是NP完全问题。对于一个单列x，当sum(x)=K且1<=numItems<=无穷时，你就会遇到子集和问题。 - Eyal Schneider

@EyalSchneider 我就有这种感觉...没想到是子集和问题，我简直不敢相信自己没看出来。如果你愿意在答案中加上这个，我会标记它的。 - Chris Kdon

Answer 1

这个问题是NP完全问题。您可以按照以下步骤将子集和问题简化为此问题。

对于子集和问题的给定输入S，k：

- 定义一个包含S中所有值的单列X - 要求k≤sum(X)≤k - 要求1≤numItems≤|S|

- Eyal Schneider