算法
(DP,01背包问题) O(nm)
可以转化为01背包问题求方案数:
- 将总和 M 看作背包容量;
- 将每个数 Ai 看作体积为 Ai 的物品;
时间复杂度
背包问题的时间复杂度是 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;
}
这里贴一个未优化的代码帮助理解
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 10010; int n, m; int f[110][N]; int main() { cin >> n >> m; //从前i个物品中选,且价值为0的方案数均为1 //什么都不选就是一种选法 for(int i = 0; i < 110; i ++) f[i][0] = 1; for(int i = 1; i <= n; i ++) { int v; cin >> v; for(int j = 0; j <= m; j ++) { //不选当前物品 f[i][j] = f[i - 1][j]; //选当前物品 //选法为从前i - 1个数中选且价值为j - v的所有选法 //即f[i - 1][j - v] if(j >= v) f[i][j] += f[i - 1][j - v]; } } cout << f[n][m] << endl; return 0; }
想了一下可以暴搜,就卡了1个数据
#include <bits/stdc++.h> using namespace std; const int N = 110; int a[N]; int cnt = 0; int n, m; void dfs(int u, int sum)//u是选第几个数,sum是当前的和 { if(u > n) return; if(sum > m) return; if(sum == m) { cnt ++; return; } dfs(u + 1, sum);//不加当前这个数 dfs(u + 1, sum + a[u]);//加当前这个数 } int main() { cin >> n >> m; for(int i = 0; i < n; i ++) cin >> a[i]; dfs(0, 0); cout << cnt << 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
orz
显式的滚动数组,可能容易理解点
#include <bits/stdc++.h> using namespace std; const int N = 10005; int f[2][N]; // f[i][j]表示从前i个数中选择, 和为j的方案数 int a[105]; int main() { int n, m; cin >> n >> m; for(int i = 0; i < 2; i++) f[i][0] = 1; // 什么也不选这是一种选法 for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { f[i & 1][j] = f[i - 1 & 1][j]; if(j >= a[i]) { f[i & 1][j] += f[i - 1 & 1][j - a[i]]; } } cout << f[n & 1][m] << endl; return 0; }
#include <iostream> #include <cstring> using namespace std; const int N = 110; int n, m; int a[N], dp[10010]; int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> a[i]; for (int i = 1; i <= n; i ++ ) { for (int j = m; j >= a[i]; j -- ) { dp[j] += dp[j - a[i]]; } dp[a[i]] ++; } cout << dp[m] << endl; return 0; }
没有初始化的版本,dp[i][j] 表示和yxc一样
f[j]+=f[j-v]的意思是总和为j并且包括v这个数,那么他的方案数就是减掉v的和的方案数的总和相加?
就是完全背包嘛
01背包
太强了,完全看不懂[捂脸]
哈哈哈哈 好真实😂😂
为什么是f[j]+=f[j-v]
这里有视频讲解:AcWing 278. 数字组合)