二维费用01背包(至少体积j)

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

参考文献

算法提高课

AC代码

#include <cstring>
#include <iostream>

using namespace std;

const int N = 25, M = 80, K = 1e3 + 10;

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

int main()
{
    //读入
    cin >> m >> o >> n;
    for (int i = 1 ; i <= n ; i ++) cin >> v1[i] >> v2[i] >> w[i];

    //初始化
    memset(f, 0x3f, sizeof f);
    f[0][0][0] = 0;
    for (int i = 0 ; i <= n ; i ++) f[i][0][0] = 0;

    //DP
    for (int i = 1 ; i <= n ; i ++){
        for (int j = 0 ; j <= m ; j ++){
            for (int k = 0 ; k <= o ; k ++){
                f[i][j][k]  = f[i - 1][j][k];
                f[i][j][k] = min(f[i][j][k], f[i - 1][max(0, j - v1[i])][max(0, k - v2[i])] + w[i]);

            }
        }
    }

    //输出
    cout << f[n][m][o] << endl;

    return 0;
}