wlacm 动态规划-潜水员 题解

题目描述

潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入

第一行有2整数m,n（1<=m<=21,1<=n<=79）。它们表示氧，氮各自需要的量。

第二行为整数k（1<=n<=1000）表示气缸的个数。

此后的k行，每行包括ai，bi，ci（1<=ai<=21，1<=bi<=79，1<=ci<=800）3整数。这些各自是：第i个气

缸里的氧和氮的容量及汽缸重量。

输出

仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。

样例输入 Copy

5 5 9 1 1 12 3 1 52 1 3 71 2 1 33 3 2 86 2 3 91 2 2 43 3 3 113 1 2 28

样例输出 Copy

104

解题思路

也是多个条件的背包问题，要注意的是dp【0】【0】是没拿取东西的状态，重量应该赋值为0 因为要求的是最小质量，所以dp数组要初始化为无穷大

代码

#include"bits/stdc++.h"
using namespace std;
int dp[1010][1010];
int o[1010],n[1010],w[1010];
int main(){
	int O,N;
	int num;
	cin>>O>>N>>num;
	for(int i=1;i<=num;i++){
		cin>>o[i]>>n[i]>>w[i];
	}
	memset(dp,127,sizeof(dp));//memset按位赋值127等同于无穷大，128就是无穷小
	dp[0][0]=0;//如果没装东西，重量应该是0，关键的处理 
	for(int i=1;i<=num;i++){
		for(int j=O;j>=0;j--){
			for(int k=N;k>=0;k--){
				int temp1=min(j+o[i],O);//当总量大于需求量时，就是可取解，直接进行重量的比较
				int temp2=min(k+n[i],N);
				dp[temp1][temp2]=min(dp[temp1][temp2],dp[j][k]+w[i]);
			}
		}
	}
	cout<<dp[O][N]<<endl;
}