分析:
f[I, j ]: 从前i个物品中选择,总体积不超过j的最大价值
g[I, j]: 价值是最大(物品体积不超过j) 的方案数
为什么g[1~v]赋初始值1, 就代表恰好是最大价值的方案数?
初始方案(什么也不装)就是1,由于g定义的是物品体积不超过j的最大值的方案数,
所以和0/1背包求方案数不同,g1~gv = 1都代表什么都不放的情况,相当于g[0] = 1
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N],g[N], a[N];
int main()
{
int N, V;cin >> N >> V;
for(int i = 0; i <= V; ++i)g[i] = 1;
for(int i = 1; i <= N; ++i)
{
int v, w; cin >> v >> w;
for(int j = V; j >= v; j--)
{
int cnt = 0;
int maxv = max(f[j], f[j - v] + w);
if(maxv == f[j])cnt += g[j];
if(maxv == f[j - v] + w)cnt += g[j - v];
f[j] = maxv;
g[j] = cnt % mod;
}
}
// cout <<f[V] <<endl;
cout << g[V] <<endl;
return 0;
}