AcWing 11：背包问题求方案数 ← 0-1背包

【题目来源】
https://www.acwing.com/problem/content/11/

【题目描述】
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最优选法的方案数。注意答案可能很大，请输出答案模 10^9+7 的结果。

【输入格式】
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi，wi，用空格隔开，分别表示第 i 件物品的体积和价值。

【输出格式】
输出一个整数，表示方案数模 10^9+7 的结果。

【数据范围】
0<N,V≤1000 
0<vi,wi≤1000

【输入样例】
4 5
1 2
2 4
3 4
4 6

【输出样例】
2

【算法分析】
设 f[i] 为背包容积为 i 时的最佳方案的总价值，cnt[i] 为背包容积为 i 时总价值为最佳的方案数。
由于背包里什么也不装也是一种方案，故初始化所有的 cnt{i] 为 1。
如果装新物品的方案总价值更大，那么用 f[j-vol]+val 来更新 f[j]，用 cnt[j-vol] 更新 cnt[j]。
如果总价值相等，那么最大价值的方案数就多了 cnt[j-vol] 种。

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int MOD=1e9+7;
const int N=1e3+5;
int f[N],cnt[N];int main() {int n,v;cin>>n>>v;for(int i=0; i<=v; i++) cnt[i]=1;for(int i=1; i<=n; i++) {int vol,val;cin>>vol>>val;for(int j=v; j>=vol; j--) {int t=f[j-vol]+val;if(t>f[j]) {f[j]=t;cnt[j]=cnt[j-vol];} else if(t==f[j]) {cnt[j]=(cnt[j]+cnt[j-vol])%MOD;}}}cout<<cnt[v]<<endl;return 0;
}/*
in:
4 5
1 2
2 4
3 4
4 6out:
2
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/147326357
https://blog.csdn.net/hnjzsyjyj/article/details/147333181
https://www.acwing.com/solution/content/3999/