$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题与一般的求方案问题不同

一般求方案的定义：考虑前 $i$ 个物品，在背包体积不超过 $j$ 的情况下的所有选择，属性为所有选择的数量（方案数）

这道题求的是最优选法的方案，即：考虑前 $i$ 个物品，在背包体积不超过 $j$ 的情况下的所有选择，属性为所有选择中使价值总和最大的方案数

我们依旧是从 01 背包的状态转移方程来看，$f[i][j]=max(f[i-1][j],f[i-1][j-v]+w)$

由于我们要让价值达到最大，因此我们需要看 $f[i][j]$ 是从哪个状态转移过来的，然后额外用一个表示方案数的数组来记录即可

最优解为 $f[m]$ ，我们最后看 $f[i]$ 在不同体积下是否有能过达到最大值的，如果是，将 $g[i]$ 累加起来

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N], g[N];
int n, m;

int main()
{
    cin >> n >> m;
    g[0] = 1; 
    for(int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = m; j >= v; j--)
        {
            int maxv = max(f[j], f[j - v] + w);
            int cnt = 0;
            if(maxv == f[j]) cnt = g[j] % mod;
            if(maxv == f[j - v] + w) cnt = (cnt + g[j - v]) % mod;
            f[j] = maxv, g[j] = cnt;//如果第一个if没有进入的话，cnt = 0
        }
    }
    int ans = 0;
    for(int i = 0; i <= m; i++)
        if(f[i] == f[m]) ans = (ans + g[i]) % mod;
    cout << ans << endl;
    return 0;
}

另一种做法：

这里我们可以调整 $f[i][j]$ 的定义：考虑前 $i$ 个物品，体积恰好为 $j$ 的情况下，达到最大价值的方案数

由于体积变为恰好，因此我们需要初始化 $f[0][0]=0$，其余全部为最小值（这道题是求最大值，因此初始化为最小值）

由于体积变为恰好，因此 $f[m]$ 不再是价值最大的解，我们需要额外遍历一遍 $f[n][j]$ 找到价值最大的数的下标，并重复上面的最后一个步骤

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N], g[N];
int n, m;

int main()
{
    cin >> n >> m;
    memset(f, -0x3f, sizeof f);
    f[0] = 0;
    g[0] = 1; 
    for(int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = m; j >= v; j--)
        {
            int maxv = max(f[j], f[j - v] + w);
            int cnt = 0;
            if(maxv == f[j]) cnt = g[j] % mod;
            if(maxv == f[j - v] + w) cnt = (cnt + g[j - v]) % mod;
            f[j] = maxv, g[j] = cnt;//如果第一个if没有进入的话，cnt = 0
        }
    }
    int idx = 0;
    for(int i = 0; i <= m; i++)
        if(f[i] > f[idx]) idx = i;
    int ans = 0;
    for(int i = 0; i <= m; i++)
        if(f[i] == f[idx]) ans = (ans + g[i]) % mod;
    cout << ans << endl;
    return 0;
}