用動態編程計算子集總和（揹包）中的子集解決方案的數量

Question

所以我想知道如何計算揹包問題的所有解決方案。也就是說，我有興趣從一組最大尺寸爲K的數字中找到可能的子集數量。

例如，我們有一組尺寸爲{3,2,5,6,7}的項目和最大尺寸爲K = 13，所以解爲{5,6,2}和{6,7}。另一方面有兩個解決方案;我想我的動態編程算法報告有兩種可能的解決方案。

Answer 1

這可以通過動態編程來完成。其基本戰略是建立一個記憶表，d[i][j]，存儲使用第一j數字，總和i組合數注意j = 0表示空組數字的下面是一個示例實現：。

int countCombinations(int[] numbers, int target) { 
    // d[i][j] = n means there are n combinations of the first j numbers summing to i. 
    int[][] d = new int[target + 1][numbers.length + 1]; 

    // There is always 1 combination summing to 0, namely the empty set. 
    for (int j = 0; j <= numbers.length; ++j) { 
     d[0][j] = 1; 
    } 

    // For each total i, calculate the effect of using or omitting each number j. 
    for (int i = 1; i <= target; ++i) { 
     for (int j = 1; j <= numbers.length; ++j) { 
      // "First j numbers" is 1-indexed, our array is 0-indexed. 
      int number = numbers[j - 1]; 

      // Initialize value to 0. 
      d[i][j] = 0; 

      // How many combinations were there before considering the jth number? 
      d[i][j] += d[i][j - 1]; 

      // How many things summed to i - number? 
      if (i - number >= 0) { 
       d[i][j] += d[i - number][j - 1]; 
      } 
     } 
    } 

    // Return the entry in the table storing all the number combos summing to target. 
    return d[target][numbers.length - 1]; 
} 

只需添加一些Google關鍵字：這個問題也被稱爲總和n個硬幣而不重複到目標總和。

Answer 2

該任務有一個動態揹包解決方案。在dp數組中，dp [i]存儲其總和爲「i」的子集數。在這種情況下，你的答案是DP [K]。（對不起，壓痕問題，我無法弄清楚如何作出正確的:(）

dp[0] = 1 ; for(int i=0; i<N ; i++) for(int j=K-a[i] ; j>=0 ; j--) dp[j+a[i]] += dp[j]