题解 P1794 【装备运输】

· · 题解

STEP 1 分析题意

首先，这道题告诉你了总体积和总重量，告诉你了每个物品的价值的重量以及体积。这不就是01背包的进阶版吗！

01背包是什么？用数组记录最佳情况，再考虑放与不放的问题。所以这道题虽然多了一个条件，也只是相当与数组要多开一维而已。依然用滚动数组搞定即可。

但是注意：枚举体积和重量的时候，一定要倒着枚举！因为一个物品只能被放入一次！当然，如果是完全背包的话，是从头枚举的！切记！切记！切记！重要的事情说三遍！

STEP 2 AC代码及注释

#include<bits/stdc++.h>//万能头文件
using namespace std;
int v,g,n,dp[501][501],h[501],t[501],z[501];//v,g,n如题所示，dp数组记录动规结果，第一维记录体积，第二维记录重量，h,t,z三个数组分别记录每个物品的体积重量和火力值 
int main(){
    scanf("%d %d\n%d",&v,&g,&n);
    for (int i=1;i<=n;i++){
        scanf("%d %d %d",&h[i],&t[i],&z[i]);
    }//正常输入
    for (int x=1;x<=n;x++){
        for (int i=v;i>=t[x];i--){
            for (int j=g;j>=z[x];j--){//体积和重量要倒着枚举，防止物品重复放入
                dp[i][j]=max(dp[i-t[x]][j-z[x]]+h[x],dp[i][j]);//动规转移方程
            }
        }
    }
    printf("%d\n",dp[v][g]);//输出当体积和重量为最大值时的火力值最大的结果
    return 0;//好习惯人人养
}

STEP 3 完结撒花！

看了我的题解，如果还有什么不懂的地方，欢迎在评论区留言哦，我会第一时间回复的。如果都懂了，就点个赞纪念一下你的点滴成长吧！