<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。
第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 最优选法的方案数。注意答案可能很大，请输出答案模 $10^9 + 7$ 的结果。
输入格式
第一行两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。
接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。
输出格式
输出一个整数，表示 方案数 模 $10^9 + 7$ 的结果。
数据范围
$0 \\lt N, V \\le 1000$
$0\\lt v_i, w_i \\le 1000$
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例：
2
思路
我们用类似求最短路的数量的方法来解决此问题。
我们只需要把$0/1$背包问题的代码改一下，加上$cnt$数组。
$cnt_i$表示体积不超过$j$的所有方案中价值$=f_i$的方案数。
枚举每一个物品，如果$f_{j-w_i}+v_i > f_j$，那么在更新$f$数组的同时，我们把$cnt_j=cnt_{j-w_i}$（想想为什么）。
如果$f_{j - i-w} + v == f_j$的话，我们要把$cnt_j+=cnt_{j-w_i}$（想想为什么）。
代码
#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
$ \begin {matrix} \mathbb {tql} & \mathbf {tql} & \mathrm {tql} \\ \mathfrak {tql} & \mathcal {tql} & \mathtt {tql} \\ \mathsf {tql} & \mathscr {tql} & \mathit {tql} \end {matrix} \raise {5 em} {\kern {-4.3 em} \overset {巨佬} \Longrightarrow} \qquad \textsf {stO} _ {\% \% \%} ^ \mathcal {stO} \kern {4 em} \raise {5em} { \% \kern {-0.5 em} \% \kern {-0.5em} \% \texttt {stO} \texttt { Zcr} \texttt {Orz} \% \kern {-0.5 em} \% \kern {-0.5em} \% } \kern {-12.5em} \mathcal {\Large {stO}} \underset {\textrm {AKIOI}} {\overset {\% \% \%} \nearrow} \kern {5.5 em} \underset {\textrm {AKIOI}} {\overset {\% \% \%} \nwarrow} \mathcal {\Large {Orz}} \kern {1em} _ {\% \% \%} ^ \mathcal {Orz} \textsf {Orz} \qquad \begin {matrix} \mathbb {tql} & \mathbf {tql} & \mathrm {tql} \\ \mathfrak {tql} & \mathcal {tql} & \mathtt {tql} \\ \mathsf {tql} & \mathscr {tql} & \mathit {tql} \end {matrix} \raise {5 em} {\kern {-4.3 em} \overset {巨佬} \Longleftarrow} $