約束和算法

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：

• 定義一個包含所有值的單個列X S中
• 要求k<=sum(X)<=k
• 要求1<=numItems<=|S|