P1794 装备运输 题解

难度：⭐⭐
知识点：背包
题目链接

序言：做水一道背包练练手~

1. 入手程序

01背包，三重限制，直接开整~

2. 编程思路

唉，说实话，这个题没什么难点，但这儿总不能空着吧?
给个01背包模板吧

for(int i=1;i<=n;i++)
{
	for(int j=v;j>=v[i];j--)
	{
		for(int k=u;k>=u[i];k--)
		{
			//重复限制个数-1次
			//动态转移方程
		}
	}
}

3. AC代码

//V和G表示最大体积和重量
//N表示仓库有N件装备
//每行3个数hi ti zi表示各装备的火力值、体积和重量
#include<bits/stdc++.h>
using namespace std;
int v,g,n;
int h[505],t[505],z[505];
int dp[505][505];
int main()
{
	cin>>v>>g>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i]>>t[i]>>z[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=v;j>=t[i];j--)
		{
			for(int k=g;k>=z[i];k--)
			{
				dp[j][k]=max(dp[j-t[i]][k-z[i]]+h[i],dp[j][k]);//动态转移方程 
			}
		}
	}
	cout<<dp[v][g]; 
	return 0;
}

我是千文杜博，记住我呦~~

The end