洛谷 P1507：NASA的食物计划 ← 二维费用0/1背包问题

【题目来源】https://www.luogu.com.cn/problem/P1507【题目背景】NASA美国航空航天局因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋因此在各方压力下终止了航天飞机的历史但是此类事情会不会在以后发生谁也无法保证。所以在遇到这类航天问题时也许只能让航天员出仓维修。但是过多的维修会消耗航天员大量的能量因此 NASA 便想设计一种食品方案使体积和承重有限的条件下多装载一些高卡路里的食物。【题目描述】航天飞机的体积有限当然如果载过重的物品燃料会浪费很多钱每件食品都有各自的体积、质量以及所含卡路里。在告诉你体积和质量的最大值的情况下请输出能达到的食品方案所含卡路里的最大值当然每个食品只能使用一次。【输入格式】第一行 2 个整数分别代表体积最大值 H 和质量最大值 T。第二行 1 个整数代表食品总数 n。接下来 n 行每行 3 个数 体积 hi质量 ti所含卡路里 ki。【输出格式】一个数表示所能达到的最大卡路里int 范围内​​​​​​​【输入样例】320 3504160 40 12080 110 240220 70 31040 400 220【输出样例】550【数据范围】对于 100% 的数据HThiti≤400n≤50ki≤500。【算法分析】● 本题与“AcWing 8二维费用的背包问题”https://blog.csdn.net/hnjzsyjyj/article/details/126230183代码基本一致。调整数据的输入顺序即可。● 本题中体积最大值 H 和质量最大值 T均达到 400故二维数组 f 的每个维度至少都要大于 400。否则会导致没有输出结果。●​​​​​​​ 二维费用的背包问题是指每个物品 i 都会同时消耗两种相互独立的资源消耗量分别为 vol[i]上限为 V 和 wht[i]上限为 W且装入该物品可获得价值 val[i]。问在不超过背包对这两类资源上限 V 和 W 的前提下应如何选择物品装入背包才能使得总价值最大。● 二维费用背包是背包问题的重要扩展形式其核心特征在于双资源约束。正因如此在求解时我们通常采用二维数组来表示满足双资源约束下的最大价值这便是二维动态规划实现。而根据物品选取规则的不同二维费用背包又可进一步分为二维费用 0/1 背包、二维费用完全背包、二维费用多重背包等典型类型。● 二维费用 0/1 背包问题1令 c[i][j][k] 表示将前 i 种物品装入限制条件 vol 为 j、限制条件 wht 为 k 时可获得的最大价值。类比于求解普通 0/1 背包问题状态转移方程的思路可得二维费用 0/1 背包问题的状态转移方程为c[i][j][k]max(c[i−1][j][k], c[i−1][j−vol[i]][k−wht[i]]val[i])2优化为二维后的二维费用的 0-1 背包问题的状态转移方程为c[j][k]max(c[j][k], c[j−vol[i]][k−wht[i]]val[i])3二维费用 0/1 背包问题核心代码for(int i1; in; i) { for(int jV; jvol[i]; j--) { //逆序 for(int kW; kwht[i]; k--) { //逆序 f[j][k]max(f[j][k],f[j-vol[i]][k-wht[i]]val[i]); } } } coutf[V][W]endl;● 二维费用完全背包与二维费用0/1背包的核心代码差异仅体现在资源约束的遍历顺序上二维费用完全背包采用正序遍历二维费用0/1背包采用逆序遍历。二维费用完全背包问题核心代码如下所示。for(int i1; in; i) { for(int jvol[i]; jV; j) { //正序 for(int kwht[i]; kW; k) { //正序 f[j][k]max(f[j][k],f[j-vol[i]][k-wht[i]]val[i]); } } } coutf[V][W]endl;【算法代码】#include bits/stdc.h using namespace std; const int N5e25; int f[N][N]; int vol[N],wht[N],val[N]; int main() { int n,V,W; cinVWn; for(int i1; in; i) { cinvol[i]wht[i]val[i]; } for(int i1; in; i) { for(int jV; jvol[i]; j--) { for(int kW; kwht[i]; k--) { f[j][k]max(f[j][k],f[j-vol[i]][k-wht[i]]val[i]); } } } coutf[V][W]endl; return 0; } /* in: 320 350 4 160 40 120 80 110 240 220 70 310 40 400 220 out: 550 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/126230183