AcWing
11. 背包问题求方案数
在dp方面，按一般的01背包问题处理。维护一个cnt数组，初始时，每种容量对应价值的方案cnt==1(什么都不取的一种方案)。当dp数组中某一容量的价值更新到更大值时，更新该容量的cnt数组值，cnt[j] = cnt[j-v]；当有一另外的一种f[j-v] + w，使得f[j-v] + w == f[j]，那么令cnt[j] += cnt[j-v]，因为对应j-v容量下的每一种方案，通过该次迭代的物品，都能转移到j容量下。最后输出f[m].
这样做的合理性在于，f[m]一定对应最大价值；所有能达到最大价值的方案，其容量也一定在m以内，一定会被归纳到cnt[m]以内。
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int M = 1010, MOD = 1e9 + 7;
int v, w;
int f[M], cnt[M];
int main(){
cin >> n >> m;
for(int i = 0; i <= m; i++) cnt[i] = 1;
for(int i = 1; i <= n; i++){
cin >> v >> w;
for(int j = m; j >= v; j--){
if(f[j - v] + w > f[j]){
f[j] = f[j - v] + w;
cnt[j] = cnt[j - v];
}
else if(f[j - v] + w == f[j]) cnt[j] = (cnt[j] + cnt[j - v]) % MOD;
}
}
cout << cnt[m] << endl;
return 0;
}