AcWing 8. 二维费用的背包问题

题目传送门
这道题目跟 \(01\) 背包很像，只不过是在 \(01\) 背包的基础上加上了一个重量限制。

\(01\) 背包的动态转移方程是

\(f[i, j] = max (f[i ? 1, j], f[i ? 1, j ? v_i] + w_i)\)

那么这个多了个重量，那么可以再开一维，变成三维

\(f[i, j, k] = max (f[i ? 1, j, k], f[i ? 1, j ? v_i, k ? m_i] + w_i)\)

同 \(01\) 背包，它也可以压缩一下空间，于是变成了

\(f[j][k] = max(f[j - v[i]][k - m[i]] + w[i], f[j][k])\)
动态转移方程出来了，那么写代码也就轻松了。

#include 

using namespace std;
const int N = 1010;
int n;//n个物品
int V;//体积上限
int M;//重量上限
int v[N];//每个物品的体积
int m[N];//每个物品的重量
int w[N];//每个物品的价值
int f[N][N];//二维的dp数组，描述前i个物品

signed main() {
    cin >> n >> V >> M;
    //体积，重量，价值
    for (int i = 1; i <= n; i++) cin >> v[i] >> m[i] >> w[i];
    //遍历每一个物品
    for (int i = 1; i <= n; i++)
        for (int j = V; j >= v[i]; j--)//由大到小遍历每一个体积
            for (int k = M; k >= m[i]; k--)//由大到小遍历每一个重量
                f[j][k] = max(f[j - v[i]][k - m[i]] + w[i], f[j][k]);//动态转移方程，01 背包的思路
    //输出
    printf("%",f[V][M]);
}