题解 P1794 【装备运输_NOI导刊2010提高（04）】

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 576 | 阅读时长 ≈ 1 分钟

一道01背包模板题吧。。。其实就是再增加了一个体积参数

状态转移方程：

$F_{j,k}=max(F_{j-v_{i},k-g_{i}}+t_{i},F_{j,k})$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int V,G,n;//V和G为最大体积和重量
int t[510],v[510],g[510];
int f[510][510];
int main()
{
	ios::sync_with_stdio(false);
	cin>>V>>G;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>t[i]>>v[i]>>g[i];
	for(int i=1;i<=n;i++)
	  for(int j=V;j>=v[i];j--)
	    for(int k=G;k>=g[i];k--) 
	      f[j][k]=max(f[j-v[i]][k-g[i]]+t[i],f[j][k]);//状态转移方程
	cout<<f[V][G];//f[V][G]即为答案
	return 0;
}