子集总和方法总数的递归关系

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

一旦编写了递归函数，我们需要添加以使其高效的所有内容就是缓存 return 值。修改是：在进行递归调用之前，检查使用这些参数的计算是否尚未完成。

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]

不同的是一个是top-bottom，一个是bottom-top

子集总和方法总数的递归关系

Recurrence relation for total number of ways to subset sum

algorithm

recursion

recurrence

subset-sum