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

$f[i][j]$ 定义：在前 $i$ 个物品当中选择，在总体积不超过 $j$ 的情况下的最大价值

考虑与 01 背包相同的处理方式，对第 $i$ 个物品的选择次数做划分，有：

• 选择 0 次：$f[i-1][j]$

• 选择 1 次：$f[i-1][j-v]+w$

• 选择两次：$f[i-1][j-2v]+2w$

• 选择 $s$ 次：$f[i-1][j-sv]+sw$ （这里的 $s$ 次表示在背包体积为 $j$ 下，第 $i$ 个物品的最大选择次数）

即：$f[i][j]=max(f[i-1][j],\color{red}{f[i-1][j-v]+w,f[i-1][j-2v]+2w,\dots ,f[i-1][j-sv]+sw})$

我们往后写一位，有：$f[i][j-v]=max(\color{red}{f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w,\dots ,f[i-1][j-sv]+(s-1)w})$

为什么最后一项是 $f[i-1][j-sv]+(s-1)w$ ?

这是因为在体积为 $j$ 的条件下，物品 $i$ 最大的选择次数只能到 $s$ 次，那么在体积为 $j-v$ 的条件下，物品 $i$ 只能选择 $s-1$ 次，这正好对应后面是加上 $(s-1)w$

对比上面两个式子，不难发现有颜色的部分都是相同的，只是差一个偏移量

因此我们有：$f[i][j]=max(f[i-1][j],f[i][j-v]+w)$

完整代码：

#include <iostream>

using namespace std;

const int N = 1010;

int v[N], w[N];
int f[N][N];
int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j - v[i] >= 0) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}

因为这里只使用了第 $i$ 层和第 $i-1$ 层，同样可以考虑空间优化

由于对 $f[i][j]$ 的更新需要使用上一层 $j$ 出的值以及本层 $j-v[i]$ 处的值，前者是未更新的，后者是已更新的

因此我们可以直接从前往后遍历，这样当我们要对 $f[j]$ 进行赋值时，原先的值可以表示 $f[i-1][j]$ ，而 $f[j-v[i]]$ 是本层已经更新的值

所以我们直接从前往后遍历即可

完整代码：

#include <iostream>

using namespace std;

const int N = 1010;

int v[N], w[N];
int f[N];
int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++)
        for(int j = v[i]; j <= m; j++)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    cout << f[m] << endl;
    return 0;
}