AcWing 11. 背包问题求方案数
原题链接
中等
作者:
rushhhhh
,
2021-02-11 14:09:07
,
所有人可见
,
阅读 356
#include <iostream>
#include <climits>
using namespace std;
const int N = 1010;
int n, m;
// f、g分别表示体积恰好为i时的最佳价值和方案数
int f[N], g[N];
int mod = 1e9 + 7;
int main()
{
cin >> n >> m;
// 体积为0时的方案数为1,即什么都不选
g[0] = 1;
// 初始化其他方案数
for(int i=1; i<=m; i++)
f[i] = INT_MIN;
// 更新最大价值的同时更新方案数
for (int i = 0; i < n; ++i)
{
int v, w;
cin >> v >> w;
// 倒着遍历(因为是一维dp)
for(int j = m; j >= v; j--)
{
// s表示体积恰好为i时的方案数
// 方案数也是dp的一个过程:
// 若f[i][j] == f[i-1][j],则s = g[i-1][j]
// 即此情况下的方案数等于(i-1, j)时的方案数
// 若f[i][j] == f[i][j-v]+w,则s = g[i][j-v]
// 即此情况下的方案数等于(i, j-v)时的方案数
// 若都相等,则累加
int t = max(f[j], f[j-v]+w);
int s = 0;
if(t == f[j])
s += g[j];
if(t == f[j-v]+w)
s += g[j-v];
if(s >= mod)
s -= mod;
f[j] = t;
g[j] = s;
}
}
// 遍历得到最大价值是多少
int maxw = 0;
for (int i = 0; i <= m; ++i)
maxw = max(maxw, f[i]);
// 因为最大价值可能在不同体积的背包中同时实现
// 所以要遍历容量的背包
int res = 0;
for(int i=0; i<=m; i++)
if(maxw == f[i])
{
res += g[i];
if(res >= mod)
res -= mod;
}
cout << res << endl;
return 0;
}