給定一組n個整數，列出所有可能的子集sum> = k

給定數組形式的未排序整數集，查找所有可能的子集，其總和大於或等於常量整數k，例如： - 我們的集合爲{1,2,3}和K = 2給定一組n個整數，列出所有可能的子集sum> = k

可能子集： -

{2}, 
{3}, 
{1,2}, 
{1,3}, 
{2,3}, 
{1,2,3}

我只能認爲幼稚算法其中列出組如果總和所有子集並檢查子集是> = k或不是，但它的指數算法和列出所有子集需要O（2^N）。我可以使用動態規劃在多項式時間內解決它嗎？

來源

2013-08-06 Hidetoshi

如果你有興趣在打印或列出所有這些子集則在最壞的情況下，你可能仍然有'2^N-1'（全部拆開從空）你需要列出的子集。但是，您可以計算多項式中動態編程的數量。 – cyon

@cyon，我們如何使用動態規劃來計算這些子集的數量？ – Hidetoshi

尋找是否有一個子集合成'k'，是NP-Hard（子集和問題） - 所以，這個問題也是如此。既然你想要實際的集合，在我看來，強制產生所有子集的蠻力是最好的選擇。（可能會使用分支和綁定技術添加一些優化，但這就是關於它，IMO） – amit

列出所有的子集將仍然爲O(2^N)，因爲在最壞的情況下，您可能仍然需要列出除空白子集之外的所有子集。

動態編程可以幫你算的有sum >= K

你去自下而上的跟蹤有多少子集從範圍[1..K]總結出一些價值的份數。像這樣的方法將是O(N*K)，這將只適用於小的K。

用動態規劃解決方案的想法最好用一個例子來說明。考慮這種情況。假設您知道在組成第一個i元素的所有集合中，您知道t1總和爲2和t2總和爲3。假設下一個i+1元素是4。考慮到所有現有的集合，我們可以通過追加元素i+1或者將其刪除來構建所有新集合。如果我們忽略它，我們得到t1子集，其總和爲2和t2子集合，總和爲3。如果我們追加它，那麼我們獲得總和爲6（2 + 4）和t2的t1子集，其總和爲7（3 + 4）。這給了我們總和爲(2,3,6,7)的子集的數量，其由第一個i+1元素組成。我們一直持續到N。

在僞代碼，這可能是這個樣子：

int DP[N][K]; 
int set[N]; 

//go through all elements in the set by index 
for i in range[0..N-1] 
    //count the one element subset consisting only of set[i] 
    DP[i][set[i]] = 1 

    if (i == 0) continue; 

    //case 1. build and count all subsets that don't contain element set[i] 
    for k in range[1..K-1] 
     DP[i][k] += DP[i-1][k] 

    //case 2. build and count subsets that contain element set[i] 
    for k in range[0..K-1] 
     if k + set[i] >= K then break inner loop      
     DP[i][k+set[i]] += DP[i-1][k] 

//result is the number of all subsets - number of subsets with sum < K 
//the -1 is for the empty subset 
return 2^N - sum(DP[N-1][1..K-1]) - 1

來源

2013-08-06 17:56:30 cyon

你能告訴我如何做到這一點部分 - >總和（DP [1 ... K] – Rasool

@Rasoolll我的意思是'sum = DP [1] + DP [2] + .. + DP [K]' – cyon

DP是一個兩層結構，維度數組，因此DP [0] + ... + DP [K]不是真的我認爲 – Rasool

我可以使用動態規劃在多項式時間內求解它嗎？

不是。問題比@amit（在評論中）更難提到。查找是否存在一個與特定k相加的子集是subset-sum problem，這是NP-hard。相反，您要求的是多少個解決方案等於特定的k，這個難度更大的類別是P#。此外，由於您不僅要計數，而且要枚舉k和目標k的所有可能子集，所以確切問題會稍微困難一些。

來源

2013-08-06 17:17:32 Hooked

如果k是0，並且該集合的每個元素都是正數，那麼您別無選擇，只能輸出每個可能的子集，所以此問題的下限爲O（2 ^N）產生輸出。

除非您知道更多關於您未告訴我們的值k的信息，否則沒有更快的通用解決方案來檢查每個子集。

來源

2013-08-06 17:20:53

給定一組n個整數，列出所有可能的子集sum> = k

回答

相關問題