和为定值的子集数
题目描述
已知 n 个正整数，wi (1≤i≤n) 形成一个集合 W={w1,w2,...,wn}，集合中的元素彼此不相同。给定某个正整数 M ，集合W中可否存在子集，该子集的所有元素之和和恰好为M，问：这样的子集有多少个？
例如，4个正整数为：
11 13 24 7
若给定M=31，则有两个子集{7,11,13}和{7,24}
于是，这样的子集有 2 个。
关于输入
第1行，输入若干个正整数，表示集合的元素，各整数之间以空格间隔；
后面有多行，每行表示一个 M 值；若某行的 M 值为0，则结束。
关于输出
对应的每个有效的 M 值，输出相应行的子集数目
例子输入
11 13 24 7 31 24 45 55 0
例子输出
2 2 0 1
解题分析
这个问题可以使用动态规划（Dynamic Programming）来解决。动态规划是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
在这个问题中，我们需要找到所有和为特定值 M 的子集的数量。我们可以使用一个二维动态规划数组 dp[i][j] 来存储到第 i 个元素为止，和为 j 的子集的数量。
这个问题的状态转移方程可以这样定义：
1. 如果当前集合的总和 M 为0，那么只有一个子集满足条件，即空子集，所以返回1。
2. 如果我们已经查看过所有的元素（i < 0），或者当前的总和 M 为负数，那么没有子集满足条件，返回0。
3. 如果当前元素 a[i] 大于当前的总和 M，那么我们不能包含这个元素，所以只能查看前 i-1 个元素，看看他们能否组成和为 M 的子集。所以 dp[i][M] = sum(i-1, M)。
4. 如果当前元素 a[i] 小于或等于当前的总和 M，那么我们有两种选择：包含这个元素或者不包含这个元素。所以 dp[i][M] = sum(i-1, M) + sum(i-1, M-a[i])。
在主函数中，我们首先使用一个循环来读取输入的元素，并将它们存储在数组 a 中。然后，我们使用另一个循环来读取输入的 M 值，并调用 sum 函数来计算满足条件的子集的数量。最后，我们将结果输出到屏幕上。
注意，为了提高效率，我们使用了记忆化搜索（也称为缓存）。我们使用一个二维数组 dp 来存储已经计算过的子问题的结果。在 sum 函数中，我们首先检查 dp[i][M] 是否已经被计算过。如果是，我们就直接返回它。否则，我们就计算它，然后将结果存储在 dp[i][M] 中，以便以后使用。
这种方法的时间复杂度是 O(n*M)，其中 n 是集合的元素数量，M 是目标和。空间复杂度也是 O(n*M)，用于存储 dp 数组。
代码实现
#include <iostream>
#include <cstring>
using namespace std;
int M, a[10000];
int len = 0;
int dp[10000][10000]={0};
int sum(int i, int M) {
if (M == 0) return 1;
if (i < 0 || M < 0) return 0;
if(dp[i][M]!=-1) return dp[i][M];
if (a[i] > M) {
dp[i][M]=sum(i-1,M);
return dp[i][M];
} else {
dp[i][M]=sum(i - 1, M) + sum(i - 1, M - a[i]);
return dp[i][M];
}
}
int main() {
char c;
memset(dp,-1,sizeof(dp));
while (cin >> a[len++]) {
c = getchar();
if (c == '\n') break;
}
while (cin >> M) {
if (M == 0) break;
cout << sum(len - 1, M) << endl;
}
return 0;
}
方法2:
解题分析2
这个问题可以使用动态规划来解决。我们可以构建一个二维数组dp，其中dp[i][j]表示使用前i个数字组成和为j的子集的数量。
初始条件是dp[i][0] = 1，表示使用前i个数字组成和为0的子集只有一种可能，即一个空集。然后我们可以根据以下状态转移方程来填充dp数组：
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]], 如果 j >= nums[i - 1]
dp[i][j] = dp[i - 1][j], 如果 j < nums[i - 1]
其中nums[i - 1]表示第i个数字。第一个条件表示我们可以选择包含第i个数字或者不包含第i个数字，第二个条件表示如果当前的和j小于第i个数字，那么我们不能选择第i个数字。
这个算法的时间复杂度是O(n * M)，空间复杂度也是O(n * M)，其中n是集合中的数字数量，M是给定的目标和。
#include <iostream>
#include <cstring>
using namespace std;
int M, a[10000];
int len = 0;
int dp[10000][10000]={0};
int main() {
char c;
while (cin >> a[len++]) {
c = getchar();
if (c == '\n') break;
}
while (cin >> M) {
if (M == 0) break;
for(int i=0;i<len;i++){
dp[i][0]=1;
}
for(int i=0;i<len;i++){
for(int j=1;j<=M;j++){
if(i==0){
if(a[i]==j){
dp[i][j]=1;
}
continue;
}
if(a[i]>j){
dp[i][j]=dp[i-1][j];
}
else{
dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];
}
}
}
cout<<dp[len-1][M]<<endl;
}
return 0;
}
