算法
(DP,01背包问题) $O(nm)$
可以转化为01背包问题求方案数:
- 将总和 $M$ 看作背包容量;
- 将每个数 $A_i$ 看作体积为 $A_i$ 的物品;
时间复杂度
背包问题的时间复杂度是 $O(nm)$。
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int n, m;
int f[N];
int main()
{
cin >> n >> m;
f[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];
}
cout << f[m] << endl;
return 0;
}
这里贴一个未优化的代码帮助理解
之前听y总讲01背包恰好装满问题,要在初始化将数组初始化为负无穷,然后f[0] = 0, 这样可以保证最后的答案是由f[0]转移过来的,那这个题也是要求恰好装满(即总和恰好达到m),这个如何保证呢
同问
您好 请问有答案了吗
这里恰好达到m是通过初始化f[0]=1,其余的f[i]=0得到的,可以保证最后的结果f[m]是由f[0]转移过来的,如果是从f[i],i不等于0的状态转移,那么最后的结果f[m]始终是0;如果想要总和是小于等于m,全部的f[i]初始化为1即可。
请问有 答案了吗
太清晰了
这里背包的意义是方案数,初始化时其他除了0外其他容量的背包都没法装满,所以方案数为0.f[0] = 1, f[i] = 0
显式的滚动数组,可能容易理解点
想了一下可以暴搜,就卡了1个数据
orz
没有初始化的版本,dp[i][j] 表示和yxc一样
f[j]+=f[j-v]的意思是总和为j并且包括v这个数,那么他的方案数就是减掉v的和的方案数的总和相加?
就是完全背包嘛
01背包
太强了,完全看不懂[捂脸]
哈哈哈哈 好真实😂😂
为什么是f[j]+=f[j-v]
这里有视频讲解:AcWing 278. 数字组合)