题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出 最优选法的方案数。注意答案可能很大,请输出答案模 109+7 的结果。
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例
2
01背包
时间复杂度 O(nm)
本题求01背包的最佳方案数,那么定义两个数组:f[N],cnt[N]
f[i] 用来存储背包容积为 i 时的最佳方案的总价值,
cnt[i]为背包容积为 i 时总价值为最佳的方案数
先初始化所有的 cnt[i] 为 1,因为背包里什么也不装也是一种方案
外层循环 n 次,每次读入新物品的 v,w
求出装新物品时的总价值,与不装新物品时作对比
如果装新物品的方案总价值更大,那么用 f[j−v]+w 来更新 f[j],用 cnt[j−v] 更新 cnt[j]
如果总价值相等,那么最大价值的方案数就多了 cnt[j−v] 种
C++ 代码
#include<cstdio>
const int N = 1010, mod = 1e9 + 7;
int f[N], cnt[N];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i <= m; i ++) cnt[i] = 1;
for(int i = 1; i <= n; i ++) {
int v, w;
scanf("%d%d", &v, &w);
for(int j = m; j >= v; j --) {
int value = f[j - v] + w;
if(value > f[j]) {
f[j] = value;
cnt[j] = cnt[j - v];
} else if(value == f[j]) {
cnt[j] = (cnt[j] + cnt[j - v]) % mod;
}
}
}
printf("%d", cnt[m]);
return 0;
}
- 代码格式略做更新2022.05.19
我觉得不是不超过,是因为cnt数组降成一维后迷惑性太明显,如果用二维解释就通了,实际上初始化的是没有物品即物品数量=0时候的1-V体积的方案数,因为没有物品,所以方案就是什么都不放(1一种方案),最优价值为0
#include<iostream> using namespace std; const int maxn = 1010; const int mod = 1e9+7; int dp[maxn][maxn],count[maxn][maxn]; int main(){ int N,V,v,w; cin>>N>>V; for(int i = 0;i<=V;i++){ count[0][i] = 1; } for(int i = 1;i<=N;i++){ cin>>v>>w; for(int j = V;j>=0;j--){ if(j<v) { count[i][j] = count[i-1][j]; dp[i][j] = dp[i-1][j]; } else { if(dp[i-1][j-v]+w>dp[i-1][j]) count[i][j] = count[i-1][j-v]; else if(dp[i-1][j-v]+w==dp[i-1][j]) count[i][j] = (count[i-1][j]+count[i-1][j-v])%mod; else count[i][j] = count[i-1][j]; dp[i][j] = max(dp[i-1][j],dp[i-1][j-v]+w); } } } cout<<count[N][V]<<endl; return 0; }
之后再降成一维
请问这个初始化为啥是for(int i=0;i<=m;i++) cnt[0][i]=1;
0种物品无论空间多少只有一种方案就是不放
f[i][j],g[i][j]的含义是什么呢
佬,为啥不是cnt[i][0]等于1呢,从前i个物品中选体积为0的方案不是也是只有不选这一种么
为什么用倒序呢
我也觉得博主的写法是定义
cnt[i]
为不超过时候的方案数。如果定义成恰好,初值和答案部分应该是像y总那样。我觉得背包体积为i与物品体积不超过i是等价的,博主说的是背包体积为i,但没说要刚好选满i体积的物品
不是等价的定义不一样首先,其次你们就是因为状态转移方程一样就出现误区了,根据定义你会发现题目的起点初始化是不一样的啊,俩个都可以,y是讲错了都是不重不漏的
都是可以的,根据定义你会发现题目的起点初始化是不一样的啊,俩个都可以,y是讲错了都是不重不漏的
没看题解写了一个不超过的的代码,和博主的代码一样的,感觉这题不超过反而好写~
这个题解到底有什么问题?看不出来,气死人了
太吊了
memset(cnt,1,sizeof cnt);
为什么这样初始化就不行呢哎
memset是按字节赋值,每个int是4个字节,这样会赋值成
00000001000000010000000100000001
大佬这样会有什么区别吗?不还是1吗?
这个数当然不是1,1是
00000000000000000000000000000001
懂了懂了,谢谢大佬
ac不了啊
能啊
为什么我用这个代码提交wa了啊
%%%
Orz
能帮我看看二维的哪错了吗
二维的有什么问题?
#include<iostream> #include<cstring> using namespace std; const int N = 1010, mod = 1e9 + 7; int cnt[N][N], f[N][N]; int v[N], w[N]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) { scanf("%d%d", &v[i], &w[i]); } memset(cnt, 1, sizeof cnt); for(int i = 1; i <= n; i++) for(int j = 0; j <= m; j++) { int value = f[i - 1][j]; if(j >= v[i]) { if(value > f[i - 1][j - v[i]]) { f[i][j] = value; cnt[i][j] = cnt[i - 1][j]; }else if(value == f[i - 1][j - v[i]]) { f[i][j] = value; cnt[i][j] = (cnt[i - 1][j] + cnt[i - 1][j - v[i]]) % mod; }else { f[i][j] = f[i - 1][j - v[i]]; cnt[i][j] = cnt[i - 1][j - v[i]]; } }else { f[i][j] = value; cnt[i][j] = cnt[i - 1][j]; } } cout << cnt[n][m] << endl; return 0; }
你去看看memset的用法.....
这个memset和我以前一样了,hh
memset初始化不能赋值1
#include <iostream> #include <cstring> using namespace std; const int N = 1010, mod = 1e9 + 7; int cnt[N][N], f[N][N]; int v[N], w[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { scanf("%d%d", &v[i], &w[i]); } // memset(cnt, 1, sizeof cnt); for (int i = 0; i < N; i++) cnt[i][0] = 1; for (int i = 0; i < N; i++) cnt[0][i] = 1; for (int i = 1; i <= n; i++) for (int j = 0; j <= m; j++) { int value = f[i - 1][j]; if (j >= v[i]) { if (value > f[i - 1][j - v[i]]+w[i]) { f[i][j] = value; cnt[i][j] = cnt[i - 1][j]; } else if (value == f[i - 1][j - v[i]]+w[i]) { f[i][j] = value; cnt[i][j] = (cnt[i - 1][j] + cnt[i - 1][j - v[i]]) % mod; } else { f[i][j] = f[i - 1][j - v[i]]+w[i]; cnt[i][j] = cnt[i - 1][j - v[i]]; } } else { f[i][j] = value; cnt[i][j] = cnt[i - 1][j]; } } cout << cnt[n][m] << endl; return 0; }
为什么这里用memset不对
现在是第一行第一列设置为1,不是全都是1、
我发现一个问题,就是acwing里面的所有数据好像都有点弱,😄
博主的f[i]用来存储背包容积为i时的最佳方案的总价值,但如果设置成体积恰好为i的话不应该初始化f[i]为负无穷吗,因为不能保证所的f[i]都被凑出来,这里是不是应该写成体积不超过i
容器恰好v相当于体积不超过v
😢如果01背包求解体积恰好是i的最大价值不应该初始化吗
我个人感觉这里的题解是有问题的,博主的状态定义是恰好,结果却写了不超过的代码。如果状态是 体积恰好是v,那么只用初始化cnt[0] = 1,如果状态定义是 体积不超过v,那么就需要 for (int i = 0; i < v; ++i) cnt[i] = 0了
容器恰好v相当于体积不超过v
转移方程是一样的,算最后答案的时候是不一样的
只在cnt[0]赋值成1为什么不对呀。
因为背包问题的f[i]是背包容积为i的时候的最大价值,相应的cnt[i]是背包容积为i的时候的凑成最大价值的方案数,无论容积是多少,什么都不装都是一种方案,所以当然要都初始化为1
滑稽佬,这
cnt[j] = (cnt[j] + cnt[j - v]) % mod;
不会有重复吗,如果是不大于j的话不会吧,cnt[ j - v ] 是 i - 1 个物品中选,应该不会重复
cnt[j]是上一层的体积为[j],那时候还没有选第i件物品的方案,没有重复~
感觉数据弱了,我初始化不小心写成
for (int i = 0; i <= n; i ++) cnt[i] = 1;
也过了
%%%
我漏掉这个了,怪不得算的不对