<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示 方案数 模 109+7 的结果。
数据范围
0ltN,Vle1000
0ltvi,wile1000
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例：
2
思路
我们用类似求最短路的数量的方法来解决此问题。
我们只需要把0/1背包问题的代码改一下，加上cnt数组。
cnti表示体积不超过j的所有方案中价值=fi的方案数。
枚举每一个物品，如果fj−wi+vi>fj，那么在更新f数组的同时，我们把cntj=cntj−wi（想想为什么）。
如果fj−i−w+v==fj的话，我们要把cntj+=cntj−wi（想想为什么）。
代码
#include <iostream>
using namespace std;
const int N = 1010,MOD = 1e9 + 7;;
int n,m;
int f[N],cnt[N];
int main () {
cin >> n >> m;
for (int i = 0;i <= m;i++) cnt[i] = 1;
for (int i = 1;i <= n;i++) {
int w,v;
cin >> w >> v;
for (int j = m;j >= w;j--) {
if (f[j - w] + v > f[j]) {
f[j] = f[j - w] + v;
cnt[j] = cnt[j - w];
}
else if (f[j - w] + v == f[j]) cnt[j] = (cnt[j] + cnt[j - w]) % MOD;
}
}
cout << cnt[m] << endl;
return 0;
}
但是为什么y总算了体积恰好为j的方案数呢??
两种写法都可以
az，自己写了一下，好像在初始化cnt的时候如果直接全变成1就会输出一个很大的数吗，可是后面好像没有用到mi呀，这是为什么呢，求解答qwq
没明白你什么意思啊qwq
全部初始化为1不会输出一个很大的数啊
是不是用了memset(cnt,1,sizeof (cnt));??
确实qwq
我觉得后面好像没有用到cnt[i] i＞m呀，为什么把后面的也初始化的就会挂呢qwq
贴个代码看看
如果用了memset(cnt,1,sizeof (cnt))的话，建议学一下memset的复制方式hh
woc我知道了，感谢，太菜了qwq
qwq
会了就好，不要在犯了hhh
tqltqltqltqltqltqltqltqltql巨佬⟹stOstO%%%%%%stO ZcrOrz%%%stO%%%↗AKIOI%%%↖AKIOIOrzOrz%%%Orztqltqltqltqltqltqltqltqltql巨佬⟸