01背包 P1507 NASA的食物计划

P1507 NASA的食物计划 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

普通01背包状态表示：f(i, j)表示前i件物品放入一个容量为j的背包可以获得的最大价值。

本题类似，f(i, j, k)表示前i件物品放入一个限制为j，且另一个限制为k的背包中可以获得的最大价值。可以进行就地滚动。

void solve() {int V,M; cin>>V>>M;int n; cin>>n;vector<array<int,3>> a(n); // V M Valfor(auto &t: a) cin>>t[0]>>t[1]>>t[2];vector<vector<int>> f(V + 1, vector<int> (M + 1));for(int i = 0; i < n; ++i) {for(int j = V; j >= a[i][0]; --j) {for(int k = M; k >= a[i][1]; --k) {f[j][k] = max(f[j][k], f[j - a[i][0]][ k - a[i][1]] + a[i][2]);}} }cout<<f[V][M];
}