自动搬运

查看原文

来自洛谷，原作者为

	翼德天尊 2019-09-26 ~ 2024-03-03

搬运于2025-08-24 21:30:24，当前版本为作者最后更新于2020-04-02 15:14:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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 完结撒花！

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