怎么创业呢白手起家,网站建设备案优化设,租房合同 模板,统计网站访问量和为定值的子集数
题目描述
已知 n 个正整数#xff0c;wi (1≤i≤n) 形成一个集合 W{w1,w2,...,wn}#xff0c;集合中的元素彼此不相同。给定某个正整数 M #xff0c;集合W中可否存在子集#xff0c;该子集的所有元素之和和恰好为M#xff0c;问#xff1a;这样的子…和为定值的子集数
题目描述
已知 n 个正整数wi (1≤i≤n) 形成一个集合 W{w1,w2,...,wn}集合中的元素彼此不相同。给定某个正整数 M 集合W中可否存在子集该子集的所有元素之和和恰好为M问这样的子集有多少个 例如4个正整数为 11 13 24 7 若给定M31则有两个子集{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 i0;ilen;i){dp[i][0]1;}for(int i0;ilen;i){for(int j1;jM;j){if(i0){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]];}}}coutdp[len-1][M]endl;}return 0;
}
