【动态规划】数组中数字和为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 100
int 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 15
1 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 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 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 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 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 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 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 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 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 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 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
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 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种方案。
![[极客大挑战 2019]PHP](https://img-blog.csdnimg.cn/direct/53ac43f480bc427ab4cb6f8c9b339d31.png)
