AcWing 8. 二维费用的背包问题
原题链接
中等
作者:
潮和
,
2024-03-14 09:48:44
,
所有人可见
,
阅读 8
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, M = 110;
int f[N][M][M];
int w[N], v[N], m[N];
int n, m1, m2; // 物品个数 最大容量 最大重量
int main(){
cin >> n >> m1 >> m2;
for (int i = 1; i <= n; i ++ )
cin >> v[i] >> m[i] >> w[i];
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <= m1; j ++ ){ // 容量
for (int k = 1; k <= m2; k ++ ){
f[i][j][k] = f[i - 1][j][k];
if (j >= v[i] && k >= m[i]){
f[i][j][k] = max(f[i -1][j][k], f[i - 1][j - v[i]][k - m[i]] + w[i]);
}
}
}
}
cout << f[n][m1][m2] << endl;
return 0;
}