题目描述

blablabla

样例

blablabla

算法1

01背包模型 时间：$O(n^3)$，空间：$O(n^2)$

该题是二维费用版的01背包问题，思路与一维费用版的一致。

首先定义状态表示：$f(i,j,k)$表示从前$i$件物品当中取，物品体积不超过$j$，物品重量不超过$k$的价值最大值。

集合划分：同样划分成不取第$i$个物品和取第$i$个物品。前者对应的状态是$f(i-1,j,k)$，后者对应的状态是$f(i-1,j-v[i],k-m[i]) + w[i]$。

因此，状态转移方程是：
$f(i,j,k) = max(f(i-1,j,k), f(i-1,j-v[i],k-m[i]) + w[i]$。

同样空间上可以优化一维：
$f(j,k) = max(f(j,k), f(j-v[i],k-m[i]))$。
其中$j$和$k$从大到小遍历。

时间复杂度

状态数时$O(n^3)$，状态计算是$O(1)$，整体$O(n^2)$。

参考文献

C++ 代码

#include <iostream>

using namespace std;

const int N = 1010, V = 110, M = 110;
int f[V][M];
int vl[N], ml[N], w[N];

int main()
{
    int n, v, m;
    cin >> n >> v >> m;
    for (int i = 1; i <= n; i++) cin >> vl[i] >> ml[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = v; j >= vl[i]; j--) {
            for (int k = m; k >= ml[i]; k--) {
                f[j][k] = max(f[j][k], f[j-vl[i]][k-ml[i]] + w[i]);
            }
        }
    }

    cout << f[v][m] << endl;
    return 0;
}