背包问题求方案数
做法等同于01背包,只是还需要维护一个数组$cnt[N]$,用来记录每一个体积的背包容量所对应的方案数
更新的方式:
1. $f[i - v] + w== f[i]$,那就加上$i - v$状态的方案数量,$cnt[i] + cnt[i - v]$,最后再取一个膜即可
2. $f[i - v] + w > f[i]$,当前容量的最优价值的需要更新,那么对于的方案数$cnt[i] = cnt[i - v]$
最后的结果就是$cnt[m]$
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1100, mod = 1e9 + 7;
int f[N], n , m , cnt[N];
int main () {
cin >> n >> m;
for(int i = 0; i < m; i++) cnt[i] = 1;
while(n --) {
int v,w;
cin >> v >> w;
for(int i = m; i >= v; i--) {
int val = f[i - v] + w;
if(val == f[i]) {
cnt[i] = (cnt[i] + cnt[i - v]) % mod;
} else if (val > f[i]) {
cnt[i] = cnt[i - v];
f[i] = val;
}
}
}
cout << cnt[m] << endl;
return 0;
}