查找总和等于 k 的子集的数量

Question

任何人都可以向我解释动态算法，该算法找到总和等于 k 的子集数。我在 Google 中搜索，但找不到任何简单的解释！对不起我的英语不好！这是代码：

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];
    }

Answer 1

您的 DP 解决方案应该是二维的，1 维用于求和，1 维用于元素数量。

定义此解的递归公式为：

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];

（希望我没有遇到小问题，没有对其进行测试 - 但它应该会让您了解一旦递归公式清楚后如何实现它）

Answer 2

您可以使用以下示例来查找总和等于 k 的子集的数量：

#include <iostream>

using std::cout;
using std::cin;

int count = 0,K;
void noofsubsets(int arr[], int sum, int N){
    if(N==0){
        if(sum==K)
            count++;
        return;
    }
    noofsubsets(arr, sum, N-1);
    noofsubsets(arr, sum+arr[N-1], N-1);
}

Answer 3

这是一个使用递归的解决方案... 考虑两种情况 i) 包括数组的第一个元素。 ii) 没有第一个数组元素。

`

def subSetsSumK(arr, v, k) :

    if (k == 0) :
        for value in v :
            print(value, end=" ")
        print()
        return
    
    if (len(arr)== 0):
        return
    si=0
    v1 = [] + v

    v1.append(arr[si])

    subSetsSumK(arr[1:], v1, k - arr[si])
    subSetsSumK(arr[1:], v, k)
   
def subSetsSumK(arr, k):

    v = []
    subSetsSumK(arr,v, k)


# Driver code

arr = [ 2,1,3,2 ]
k_sum = 4
subSetsSumK(arr,k)

查找总和等于 k 的子集的数量

Finding the number of subsets with sum equal to k

c++

algorithm

dynamic-programming

查找总和等于 k ​​的子集的数量

Finding the number of subsets with sum equal to k

c++

algorithm

dynamic-programming

查找总和等于 k 的子集的数量