1 题目描述
物品装入背包,总体积不超过背包容量,且总价值最大的方案数。
2 分析
注意这里要求是总体积不超过背包容量的最佳方案数,不像之前的数字组合和货币系统中,题目的要求是体积恰好是背包容量。
在之前的题目中,由于要求是体积恰好是背包容量,所以初始状态 $g[0][0] = 1$ , 代表一个物品都不选且总体积恰好是 $0$ 的方案数是 $1$, 并且在状态转移的时候一定是
$$g[i][j] = g[i - 1][j] + g[i - 1][j - v] \, \, \, j >= v$$
$$g[i][j] = g[i - 1][j] \, \, \, j < v$$
$g[i][j]$ 代表从前 $i$ 个物品选,且总体积恰好是 $j$ 的方案,可以优化到一维
$$g[j] = g[j] + g[j - v], \, \, \, j >= v$$
滚动数组实际上是在 $j < v$ 的时候 $g[j]$ 是上一轮的 $g[i - 1][g]$ 没有发生更新从而维持之前的状态。
但是这里不一样了,在这里 $g[i][j]$ 代表从前 $i$ 个物品中选择,且总体积不超过 $j$ 总价值最大的方案数
首先初始状态发生了变化,例如$g[0][0] = 1, \, g[0][1] = 1$ , $g[0][1] = 1$ 代表 $1$ 个物品都不选,且总体积不超过 $1$ 是一个合法的状态,状态转移方程也发生了变化,我们从实际出发,如下
3 coding
#include<iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N], g[N]; // f[j] 是 0 - 1背包的状态 g[j] = g[i][j] 从前 i 个物品中选择,且总体积不超过 j 总价值最大的方案数
int main()
{
int n, m;
scanf("%d%d", &n, &m);
// 状态初始化 g[0][0] = g[0][1] = g[0][2] = ... = g[0][m] = 1
for (int i = 0; i <= m; i ++ ) g[i] = 1;
for (int i = 1; i <= n; i ++ ) // 枚举物品
{
int v, w;
scanf("%d%d", &v, &w);
for (int j = m; j >= v; j -- ) // 枚举体积
{
int maxv = max(f[j], f[j - v] + w); // 枚举决策
if (f[j] < f[j - v] + w) g[j] = g[j - v];
else if (f[j] == f[j - v] + w) g[j] = (g[j] + g[j - v]) % mod; // 当前方案可以由他的两个子方案转移过来
f[j] = maxv;
}
}
printf("%d", g[m]);
}