algorithm - 约束和算法

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)

目标是找到满足此要求的所有可能组合。或者，如果这会花费太长时间，那么只需要一些非常小的子集就可以了。

我的问题是有什么好的算法可以解决这个问题吗？这不是家庭作业问题或其他任何问题，而是针对我的个人项目。我一直在想办法解决这个问题，但似乎总是以非常低效的解决方案告终。希望我遗漏了什么。

Answer 1

这个问题是 NP 完全的。您可以轻松减少 Subset-Sum这个问题如下。

对于子集求和问题的给定输入 S,k:

• 定义包含 S 中所有值的单个列 X
• 需要 k<=sum(X)<=k
• 需要 1<=numItems<=|S|