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

这道题跟 AcWing 1022. 宠物小精灵之收服 是一样的，不过这道题应该才是模板

这是二维费用的 01 背包问题，其实我们的处理思路跟 01 背包是一样的

$f[i][j][k]$ 表示集合为：所有考虑前 $i$ 个物品，在「花费1」不超过 $j$ ，「花费2」不超过 $k$ 的不同选法

属性为所有选法当中价值的最大值

由于状态从二维变成了三维，因此也需要三重循环

不难写出状态转移方程 $f[i][j][k]=max(f[i-1][j][k], f[-1][j-v1][k-v2]+w)$

其实二维费用背包问题需要注意的地方在「花费」的表示上，我们一般是用 $v_i$ 来表示「花费 $i$」

需要说明的是，这里我们采用状态压缩的写法，那么里面的两重循环都需要从后往前遍历，维数更大的情况也一样

完整代码：

#include <iostream>

using namespace std;

const int N = 110;

int f[N][N];
int n, V, M;

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