AcWing 11. 背包问题求方案数
原题链接
中等
C++ 代码
#include<iostream>
using namespace std;
const int N = 1010, mod = 1e+9 + 7;
int f[N];
long long g[N];
int w[N],v[N];
int n, V;
int main() {
cin >> n >> V;
for(int i = 0; i < n; i ++) cin >> v[i] >> w[i];
// 一开始没有物品的情况有唯一方案
for(int i = 0; i <= V; i ++) g[i] = 1;
for(int i = 0; i < n; i ++) {
for(int j = V; j >= v[i]; j --) {
int newValue = f[j-v[i]] + w[i];
// 价值变大, 一定用到了第i个物品,
if(newValue > f[j]) {
f[j] = newValue;
g[j] = g[j - v[i]];
}
// 价值不变, 用到了第i个,或者没有用到第i个
else if(newValue == f[j]) {
g[j] += g[j - v[i]];
g[j] %= mod;
}
}
}
cout << g[V] << endl;
return 0;
}