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

背包问题是一种基本模型，我们直接给出 $f[i][j]$ 的定义：

$f[i][j]$ 表示的集合为：对前 $i$ 个物品进行选择，当总体积不超过 $j$ 时的物品组合；属性为所有物品组当中价值的最大值

当我们对第 $i$ 个物品考虑时，有两种可能：

• 选择第 $i$ 个物品：我们先算去掉第 $i$ 个物品的情况，即在前 $i\ -\ 1$ 个物品当中选，价值不超过 $j\ -\ v_i$ 的物品组合，刚好就是 $f[i\ -\ 1][j\ -\ v_i]$ ，此时我们再加上第 $i$ 个物品的价值即可

• 不选择第 $i$ 个物品：那么直接在前 $i\ -\ 1$ 个物品当中选，即 $f[i\ -\ 1][j]$

完整代码：

#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 - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

我们发现，在状态转移方程中只会用到 $i$ 和 $i\ -\ 1$ ，即只需要用两层，因此可以考虑对空间进行优化

我们定义 $f[j]$ 表示对前 $i$ 个物品进行选择，当总体积不超过 $j$ 时的最大价值

由于需要用到上一次循环的结果（即 $f[i\ -\ 1]$ 层当中 $f[j-v[i]]$ 处的值，相比于 $f[j]$ 在其左边），因此我们只能从后往前进行循环，这样当对 $f[j]$ 赋值时，原先的值就是上一次循环所遗留下来的值

完整代码：

#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 = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}