《算法提高课》题解与笔记上线啦！(链接就是这个){: style=”color: #FF0000”}

创建时间2024-1-24

$$ #5 8.二维费用的背包问题 $$

二维费用背包模型

原题Link

Code:

# include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10, M = 1e2 + 10;

int n, max_c, max_m;
int c[N], m[N], w[N], f[M][M];

int main(){
    scanf("%d %d %d", &n, &max_c, &max_m); 

    for(int i = 1; i <= n; i ++) scanf("%d %d %d", &c[i], &m[i], &w[i]);

    for(int i = 1; i <= n; i ++)
        for(int j = max_c; j >= c[i]; j --)
            for(int k = max_m; k >= m[i]; k --)
                f[j][k] = max(f[j][k], f[j - c[i]][k - m[i]] + w[i]); // 压一维 

    printf("%d", f[max_c][max_m]);

    return 0;
}

思路: