题目描述
给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。
输入描述:
输入为两行:
第一行为两个正整数n(1 ≤ n ≤ 1000),sum(1 ≤ sum ≤ 1000)
第二行为n个正整数A[i](32位整数),以空格隔开。
输出描述:
输入
5 15
5 5 10 2 3
输出
4
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n, sum;
cin >> n >> sum;
vector<long>vec(sum + 1, 0), input(n + 1, 0);
vec[0] = 1;这一步的目的是如果当前数字中的元素刚好等于要求的,就是多一种方法
//如果不赋值为1,还是为0就没办法加一种方法
vector<vector<long> >result(n + 1, vec);
for (int i = 1; i <= n; i++)
{
cin >> input[i];
}
//程序多加一行的目的是,例如:result[1][5]=result[0][5]+result[0][5-input[1]](即result[0][0])
//多加一行方便整体运算不需分类计算
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= sum; j++)
{
if (j - input[i] >= 0)
{
//如果列所在数字减去该行数大于等于0,该格子内容为该列上一行数字与上一行差
// 值所在格子数量和。什么意思呢?例如(10,3),若想要用3之前的数列得到10,除了
// 它上一行(即2)本身就能得到2个10外,只要之前的数字是7,7+3依然可以得到10。因
// 此去看上一行中列数为7的格子数值,为2,即它上一个数有2中组合得到7,7+3=10。
// 那该行数值即为2+2=4。
result[i][j] = result[i - 1][j] + result[i - 1][j - input[i]];
}
else
{//果列所在数字减去该行数小于0,那么该格子继承本列上一行的数字。
result[i][j] = result[i - 1][j];
}
}
}
cout << result[n][sum] << endl;
return 0;
}
如果是使用上面的用例图解图上图所示,
然后说一下做法: 1.由于每个数总能把0填上,且0不可填上初0外其余数,所以数组第一行全填0,第一列全填1; 2.从第二行第二列开始遍历数组。如果列所在数字减去该行数小于0,那么该格子继承本列上一行的数字。例如图中(2,10)对应格子。由于让10得到2,那必须由-8+5得到,但是该题无法得到比0小的数,因此由10之前的数得到2的最多可能与他之前的数(即5)是一样的; 3.如果列所在数字减去该行数大于等于0,该格子内容为该列上一行数字与上一行差值所在格子数量和。什么意思呢?例如(10,3),若想要用3之前的数列得到10,除了它上一行(即2)本身就能得到2个10外,只要之前的数字是7,7+3依然可以得到10。因 此去看上一行中列数为7的格子数值,为2,即它上一个数有2中组合得到7,7+3=10。 那该行数值即为2+2=4。
转载于:https://www.cnblogs.com/wuyepeng/p/9672154.html