【动态规划】数组中数字和为sum的方案个数
给定一个有 n n n个正整数的数组 a 和一个正整数 s u m sum sum，求选择数组 a 中
部分数字和为 s u m sum sum的方案数。若两种选取方案有一个数字的下标不一样，则认为是不同的方案。
输入描述：输入为两行，第一行为两个正整数 a a a和 s u m sum sum，第二行为 n n n 个正整数a[i]，以空格隔开。
输出描述：输出所求的方案数。
设计算法实现上述需求，并分析算法的时间复杂度。
代码实现
#include<bits/stdc++.h>
using namespace std;#define MAX 100int a[MAX] = {5,5,10,2,3};
int n = 5,sum=15;void printNum(int num[MAX][MAX],int n,int sum);int getPro(int a[],int sum,int n)
{int res=0;int dp[MAX][MAX]={0};if(sum==0)return 0;for(int i=0;i<=n;i++){dp[i][0]=1;}printNum(dp,n,sum);for(int i=1;i<=sum;i++){dp[0][i]=0;}for(int i=1;i<=n;i++){for(int j=1;j<=sum;j++){if(a[i-1]>j){dp[i][j] = dp[i-1][j];//这时候背包已经装不下新的物品了,所以可装的物品应该不变,即继承了上一行的值即可 -> dp[i][j] = dp[i-1][j]}else{dp[i][j] = dp[i-1][j]+dp[i-1][j-a[i-1]];}}printNum(dp,n,sum);}printNum(dp,n,sum);return dp[n][sum];
}void printNum(int num[MAX][MAX],int n,int sum){cout << "\t ";for(int i=0;i<=sum;i++){printf("%2d ",i);}cout << endl;printf("\t ");for(int j=0;j<=sum;j++){printf("%2d ",num[0][j]);}cout << endl;for(int i=1;i<=n;i++){printf("a[%d]: %2d |",i-1,a[i-1]);for(int j=0;j<=sum;j++){printf("%2d ",num[i][j]);}cout << endl;}cout << endl;return;
}int main()
{int res = getPro(a,sum,n);cout << "共有" << res << "种方案。";return 0;
}
核心算法
int getPro(int a[],int sum,int n)
{int res=0;int dp[MAX][MAX]={0};if(sum==0)return 0;for(int i=0;i<=n;i++){dp[i][0]=1;}printNum(dp,n,sum);for(int i=1;i<=sum;i++){dp[0][i]=0;}for(int i=1;i<=n;i++){for(int j=1;j<=sum;j++){if(a[i-1]>j){dp[i][j] = dp[i-1][j];//这时候背包已经装不下新的物品了,所以可装的物品应该不变,即继承了上一行的值即可 -> dp[i][j] = dp[i-1][j]}else{dp[i][j] = dp[i-1][j]+dp[i-1][j-a[i-1]];}}printNum(dp,n,sum);}printNum(dp,n,sum);return dp[n][sum];
}
主循环
for(int i=1;i<=n;i++)//i从0到n{for(int j=1;j<=sum;j++)//j从1到sum,因为0位置已经赋值了{
判断新增物品的质量(v[i])
if(a[i-1]>j){dp[i][j] = dp[i-1][j];}
情况一: 新增物品的质量(v[i]) 大于所需要合成背包的质量 j
这时候背包已经装不下新的物品了,所以可装的物品应该不变,
即继承了上一行的值即可
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] ( a [ i ] > j ) dp[i][j] = dp[i-1][j]\tag{$a[i]> j$} dp[i][j]=dp[i−1][j](a[i]>j)
else{dp[i][j] = dp[i-1][j]+dp[i-1][j-a[i-1]];}
情况二: 新增的物品质量小于等于需要合成背包的质量 j
现在可构成质量为j的背包的方法数 = 上一行构成j的值 + 上一行构成j-a[i]的值
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i − 1 ] [ j − a [ i ] ] ( a [ i ] ≤ j ) dp[i][j] = dp[i-1][j] + dp[i-1][j- a[i] ]\tag{$a[i]\leq j$} dp[i][j]=dp[i−1][j]+dp[i−1][j−a[i]](a[i]≤j)
}}
运行结果
为了方便观察，采用表格展示：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[0]: 5 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[1]: 5 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[2]: 10 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[3]: 2 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[4]: 3 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[0]: 5 | 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
a[1]: 5 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[2]: 10 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[3]: 2 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[4]: 3 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[0]: 5 | 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
a[1]: 5 | 1 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0
a[2]: 10 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[3]: 2 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[4]: 3 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[0]: 5 | 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
a[1]: 5 | 1 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0
a[2]: 10 | 1 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2
a[3]: 2 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[4]: 3 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[0]: 5 | 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
a[1]: 5 | 1 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0
a[2]: 10 | 1 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2
a[3]: 2 | 1 0 1 0 0 2 0 2 0 0 2 0 2 0 0 2
a[4]: 3 | 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[0]: 5 | 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
a[1]: 5 | 1 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0
a[2]: 10 | 1 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2
a[3]: 2 | 1 0 1 0 0 2 0 2 0 0 2 0 2 0 0 2
a[4]: 3 | 1 0 1 1 0 3 0 2 2 0 4 0 2 2 0 40 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a[0]: 5 | 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
a[1]: 5 | 1 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0
a[2]: 10 | 1 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2
a[3]: 2 | 1 0 1 0 0 2 0 2 0 0 2 0 2 0 0 2
a[4]: 3 | 1 0 1 1 0 3 0 2 2 0 4 0 2 2 0 4共有：4种方案。
![[安全开发]如何搭建一款自己的网安微信机器人](https://img-blog.csdnimg.cn/img_convert/23ca4c151bc9fd030631f39cc0eb8fed.png)
