等k子集算法

Question

沒有人知道一個好的和有效的等k子集算法算法嗎？優選c或C++，其可以處理100個元素矢量，可能具有複雜性和時間估計

ex。 9元向量

X = {2,4,5,6,8,9,11,13,14}

我需要生成所有k = 3點不相交的子集與總和= 24 算法應檢查是否有k個不相交的子集與每個元件24的總和，並以升序列出它們（在子集，子集之間），或者，以查看是否該溶液不存在

解

溶液1：{ 2 8 14} {4 9 11} {5 6 13}

解決方案2：{ 2 9 13} {4 6 14} {5 8 11}

由於

Answer 1

不幸的是，限制k-subset problem is a hard problem ...如果要生成所有這樣的k子集，你沒有選擇，只能evaluate many possible candidates。

您可以執行幾項優化來減少搜索空間。

給定域x constaining整數值， 給定一個正整數目標男， 給定一個正整數k的大小爲所述子集，

1. 當x僅包含正整數，且給定的一個上界中號，從大於或等於M的x中移除所有項目。這些不可能是子集的一部分。
2. 同樣，對於k> 1，給定的M和包含正整數的x，從x中移除所有大於M + min0 + min1 ... minK的項。實質上，刪除所有不可能是子集的一部分的大值，因爲即使選擇小值，它們也會導致超過M的總和。
3. 您也可以使用偶數/奇數排除原則來削減向下搜索空間。例如，當k是奇數而M是偶數時，你知道總和將包含三個偶數或兩個奇數和一個偶數。您可以通過從x中刪除可能成爲總和的一部分的候選值來使用此信息來減少搜索空間。
4. 對向量x進行排序 - 這允許您快速排除不可能包含在總和中的值。

當矢量x包含負值時，這些優化中的很多（偶數/奇數排除除外）不再有用/無效。在這種情況下，你幾乎不得不做一個詳盡的搜索。

作爲Jilles德維特指出，如果X包含負數，你可以在X-增加值最小的絕對值X的每個成員這將所有值轉向回正的範圍內 - 使得一些我上面描述的優化可能再次。但是，這要求您能夠在擴大範圍內準確表示正值。實現此目的的一種方法是在內部使用更寬的類型（比如說long而不是int）來執行子集選擇搜索。但是，如果您這樣做，請記住在返回結果時將結果子集縮小回相同的偏移量。