子集總和的方法總數的復發關係

Question

我想找出在子集總和問題中達到目標的總數。以下是我的方法。

如果'j'個元素的總和等於'i'，則DP [i，j]爲1，否則爲0，其中'a'爲輸入。所以，

DP[i, j] = DP[i, j-1] + DP[i - a[j], j-1] 

對於輸入[10，13，15，18，20，15]和目標= 30 ;我們正在尋找DP [30,6]作爲答案。

我能夠得到它與遞歸（http://ideone.com/0sHhDL）工作，但我需要用DP做到這一點。

Answer 1

一旦編寫了遞歸函數，我們需要添加的所有函數才能使其高效，以緩存返回值。修改是：在進行遞歸調用之前，檢查具有這些參數的計算尚未完成。

int NMAX = 100; 
int cache[NMAX][NMAX]; 
int answer; 
// Returns true if there is a subset of set[] with sun equal to given sum 
int isSubsetSum(int set[], int n, int sum) 
{ 

    // Base Cases 
    if (sum == 0) { 
     answer++; 
     return 0; //return false here as we are after all the sums 
    } 
    if (n == 0 && sum != 0) 
     return 0; 

    if(cache[n][sum] == -1) { 

     // If last element is greater than sum, then ignore it 
     if (set[n-1] > sum) 
      return isSubsetSum(set, n-1, sum); 

     /* else, check if sum can be obtained by any of the following 
      (a) including the last element 
      (b) excluding the last element */ 
     cache[n][sum] = isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1]); 
    } 
    return cache[n][sum]; 
} 

// Driver program to test above function 
int main() 
{ 
    int set[] = {3, 34, 4, 12, 5, 2}; 
    int sum = 9; 
    int n = sizeof(set)/sizeof(set[0]); 
    for(int i=0; i<NMAX; i++) for(int j=0; j<NMAX; j++) 
     cache[i][j] = -1; 
    isSubsetSum(set, n, sum); 
    printf("total %d\n", answer); 
    return 0; 
} 

在代碼中，行

cache[n][sum] = isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1]); 

相當於遞歸公式

DP[i, j] = DP[i, j-1] + DP[i - a[j], j-1] 

的區別在於，一個是頂部 - 底部，另一種是底頂部。