蛙人(背包型DP) 解题日志

蛙人 (ple)

蛙人使用特殊设备潜水。设备中有一个气瓶,分两格:一格装氧气,另一格装氮气。留在水中有时间的限制,在深水中需要大量的氧气与氮气。为完成任务,蛙人必须安排好气瓶。每个气瓶可以用它的重量和含有气体的体积来描述。蛙人要完成任务,就需要特定数量的氧气与氮气。要完成任务,他所需带的气瓶的总重量最少是多少呢?
例如:蛙人有下述五个气瓶。每个气瓶表述为:氧气的体积,氮气的体积(以“升”为单位)和气瓶的重量(以“公钱(10g)”为单位):

3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

 

如果蛙人需要5升氧气和60升氮气,那么他必须带两个气瓶总重为249(例如说第一个与第二个或第四个与第五个)。

你的任务是:编一条程序,从文本文件PLE.IN读入蛙人对氧气与氮气的需求,可得气瓶的数量以及它们的描述,计算蛙人完成任务最少需要带多重的气瓶;把结果写入文本文件PLE.OUT中。

备注:给出的数据总能找到完成任务的方法

【输入格式】ple.in)

输入文件PLE.IN第一行是两个整数 t,a 用一个空格隔开,1<=t<=21 且 1<=a<=79。他们表示完成任务需要的氧气与氮气的体积。第二行有一个整数,1<=n<=1000,表示可用的气瓶数量。接下来n行是对气瓶的描述;PLE.IN的第(i+2)行包含三个整数ti, ai, wi用一个空格隔开,(1<=ti<=21, 1<=ai<=79, 1<=wi<=800)。它们表示:第i瓶中氧气与氮气的体积,以及这个气瓶的重量。

【输出格式】(ple.out)

你的程序要往输出文件PLE.OUT中的第一行写入一个整数,且输出文件只有一行。这个整数是完成任务最少需要携带气瓶的总重量。

输入样例:
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

输出样例:
249

【代码日志】

 

#include<bits/stdc++.h>
using namespace std;
int dp[101][101];
int O2,N2,n;
int o2[1005],n2[1005],w[1005];
int main(){
	memset(dp,-1,sizeof(dp));
	cin>>O2>>N2>>n;
	dp[0][0]=0;
	for(int i=0;i<n;i++){
		cin>>o2[i]>>n2[i]>>w[i];
		for(int to2=100;to2>=0;to2--){
			for(int tn2=100;tn2>=0;tn2--){
				if(dp[to2][tn2]!=-1 && (dp[to2+o2[i]][tn2+n2[i]] > dp[to2][tn2]+w[i] || dp[to2+o2[i]][tn2+n2[i]]==-1)){
					dp[to2+o2[i]][tn2+n2[i]] = dp[to2][tn2]+w[i];
				}
			}
		}
	}
	int ans=999999999;
	for(int to2=O2;to2<=100;to2++){
		for(int tn2=N2;tn2<=100;tn2++){
			if(dp[to2][tn2]!=-1 && dp[to2][tn2] < ans){
				ans = dp[to2][tn2];
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注