AcWing.278 数字组合
题目描述:
给定 $N$ 个正整数 $A_1,A_2,…,A_N$,从中选出若干个数,使它们的和为 $M$,求有多少种选择方案。
输入格式
第一行包含两个整数 $N$ 和 $M$。
第二行包含 $N$ 个整数,表示 $A_1,A_2,…,A_N$。
输出格式
包含一个整数,表示可选方案数。
数据范围
1≤$N$≤100,
1≤$M$≤10000,
1≤$A_i$≤1000,
答案保证在 $int$ 范围内。
样例:
输入样例:
4 4
1 1 2 2
输出样例:
3
算法:01背包
M看成背包容量;
把每个数看成一个物品,$A_i$看成体积;
目标:求出总体积恰好是M的方案数(Count)。
$$闫氏DP分析法:$$
状态表示:
集合:所有只从前i个物品中选,且总体积恰好是$j$的方案的集合
属性:$Count$计数
状态计算:
1.不包含物品i的所有选法
$f_{i-1,j}$;
直接用上一次选的就可以了,因为是不选物品$i$2.包含物品i的所有选法
$f_{i-1,j-v_i}$;
因为是包含物品$i$,所以每种选法都有$v_i$,所以每次先吧物品$i$的体积先$-$掉再求
总的方案为两种情况加起来:
$f_{i,j} = f_{i-1,j} + f_{i - 1,j-v_i};$
当然也可以把他优化成一维的,因为每次只用到了$i-1$,所以一个一维数组倒着推就可以了,至于为什么倒着推请参考:https://blog.csdn.net/sunshine_lyn/article/details/79482477
代码:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10010;
int n , m;
int f[N];
int main() {
cin >> n >> m;//读入
f[0] = 1;//凑成0一共有1种方案
for (int i = 0; i < n; ++ i) {
int v;
cin >> v;
for (int j = m; j >= v; -- j)
f[j] += f[j - v];//因为倒着推并且去掉了一维所以f[j]直接加f[j-v]而不用加f[i-1][j],因为优化掉了一维f[i-1][j]就是f[j],所以只加f[j - v]就可以了
}
cout << f[m] << endl;//输出
return 0;
}