求和等于k的子集的个数 [英] Finding the number of subsets with sum equal to k

问题描述

谁能给我解释一下动态算法，它找出了sum等于k的子集的数目。 我在谷歌上搜索，但找不到任何简单的解释！对不起，我的英语很差！ 代码如下：

int numbers[MAX];

int GetmNumberOfSubsets()
    {
        int dp[MAX];
        dp[0] = 1;
        int currentSum = 0;
        for (int i = 0; i < numbers.length; i++)
        {
            currentSum += numbers[i];
            for (int j = min(sum, currentSum); j >= numbers[i]; j--)
                dp[j] += dp[j - numbers[i]];
        }

        return dp[sum];
    }

推荐答案

您的DP解决方案应该是二维的，一维表示总和，一维表示元素数。

定义此解的递归公式为：

DP(x,i) = 0    x < 0
DP(0,i) = 1
DP(x,0) = 0    x > 0
DP(x,i) = DP(x-numbers[i],i-1) + DP(x,i-1)

应该是这样的：

    int dp[MAX+1][sum+1];
    int i, x;
    for (i = 0; i < MAX+1; i++) { 
         dp[i][0] = 1;
    }
    for (x = 1; x < sum+1; x++) { 
         dp[0][x] = 0
    }
    for (i = 1; i < MAX+1; i++) { 
       for (x = 1; x < sum+1; x++) { 
           dp[i][x] = dp[i-1][x];
           if (x >= numbers[i])
             dp[i][x] += dp[i][x-numbers[i]];
        }
     }
    return dp[MAX][sum];

(希望我没有遇到小问题，没有测试它--但它应该会让您知道如何在递归公式明确后实现它)

这篇关于求和等于k的子集的个数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！