二维01背包

二维费用背包，我们只需要多一维来表示多出来的限制就行。

状态表示：f[i][j][k]表示从前i个物品中选，总体积不超过j，总重量不超过k的 装入背包的最大价值。

状态的分析和01背包完全一样，而优化也和完全背包的优化完全一样，优化掉一维：

f[j][k]表示总体积不超过j，总重量不超过k，装入背包的最大价值。

f[j][k] = max(f[j][k], f[j - v1][k - v2] + w)

$ 时间复杂度O(NMK)，空间复杂度O(MK)$

参考文献

算法提高课

AC代码

#include <iostream>
using namespace std;

const int N = 110;

int f[N][N];
int n, m , o, v1 ,v2, w;

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