二维费用01背包问题，动态规划，但是要注意边界条件。

状态设定

F[i,j,k] 前i个瓶，氧为j，氮为k的最小重量

状态转移方程

F[i,j,k]=Min { F[i-1,j,k], F[i-1,j-P_O[i],k-P_N[j]] + C[i] ( j-P_O[i]>=0 ,k-P_N[j]>=0 ), C[i] ( j-P_O[i]<0 ,k-P_N[j]<0 ) }

边界条件

F[i,j,k]=无穷大 F[i,0,0]=0

目标结果

Min{F[N,i,j] | i>=T , j>=A}

上述动态规划可以用滚动数组优化，或者直接优化为二维。

/* 
 * Problem: POI1998 ple
 * Author: Guo Jiabao
 * Time: 2008.12.01 21:20:34
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=1001;
const int M_O=80;
const int M_N=M_O;
const int INF=0x7FFFFFF;

int F[2][M_O][M_N];
int P[MAXN],Q[MAXN],C[MAXN];
int N,T_O,T_N,Ans;

void init()
{
	int i,j,k;
	freopen("ple.in","r",stdin);
	freopen("ple.out","w",stdout);
	scanf("%d%d%d",&T_O,&T_N,&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d%d%d",&P[i],&Q[i],&C[i]);
	}
	for (i=0;i<=1;i++)
	{
		for (j=0;j<M_O;j++)
		{
			for (k=0;k<M_N;k++)
			{
				F[i][j][k]=INF;
			}
		}
		F[i][0][0]=0;
	}
}

void dynamic()
{
	int i,j,k,p;
	Ans=INF;
	for (i=p=1;i<=N;i++,p=!p)
	{
		for (j=1;j<M_O;j++)
		{
			for (k=1;k<M_N;k++)
			{
				F[p][j][k]=F[!p][j][k];
				if (j-P[i]<0 && k-Q[i]<0 && C[i] < F[p][j][k])
					F[p][j][k]=C[i];
				if (j-P[i]>=0 && k-Q[i]>=0 && F[!p][j-P[i]][k-Q[i]] + C[i] < F[p][j][k])
					F[p][j][k]=F[!p][j-P[i]][k-Q[i]] + C[i];
				if (i==N && j>=T_O && k>=T_N && F[p][j][k]<Ans)
					Ans=F[p][j][k];
			}
		}
	}
}

int main()
{
	init();
	dynamic();
	printf("%d",Ans);
	return 0;
}

潜水员的问题
【问题描述】

    一个潜水员在潜水时使用一种特殊的装置：一个有两个容器的气筒。一个容器中装的是氧气，另一个容器中装氮气。潜水员需要携带的氧气和氮气量依赖于潜水的时间和深度。潜水员有一系列的气筒，用来在不同的情况下携带。每个气筒可以用这样几个量来描述：气筒的质量，气筒中所能容纳的氧气量，以及可以容纳的氮气量。为了能完成最近的一个任务，潜水员需要一定量的氧气和氮气。潜水员有一系列准备好的气筒。他希望能携带总质量尽可能小的气筒下水。现在请你帮他计算一下至少要携带多少质量的气筒下水才能完成这个任务。

【示例说明】

    潜水员有以下 5 个气筒。每个气筒用三个整数来描述：气筒所能容纳的氧气的量，氮气的量和气筒的质量：

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

    如果这次任务中潜水员需要携带 5 升 氧气， 60 升 氮气。那么他至少要携带总质量为 249 的气筒下水（样例中的第一个和第二个气筒或者第四个和第五个气筒）。

【任务】

写一个程序：

•  从输入文件中读入完成任务所需要的氧气和氮气量以及气筒的个数和对每个气筒的描述。

•  计算潜水员完成任务至少需要携带的多少质量的气筒。

•  将结果写入输出文件中。

注意：题目中给出的气筒总是能够容纳足够多的气体使得潜水员能完成任务。

【输入格式】

    在文件的第一行中有两个整数 t 和 a ，分别描述完成任务所需的氧气和氮气量。（ 1 ≤ t ≤ 21 ， 1 ≤ a ≤ 79 ）。第二行中有一个整数 n ，表示气筒的个数。（ 1 ≤ n ≤ 1000 ）。以后 n 行中，每行有三个整数 t i ， a i ， w i ， t i 表示第 i 个气筒所能容纳的氧气量， a i 表示第 i 个气筒所能容纳的氮气量， w i 表示气筒 i 的质量。（ 1 ≤ a i ≤ 21 ， 1 ≤ t i ≤ 79 ， 1 ≤ w i ≤ 800 ）。

【输出格式】

    输出文件只有一行，这行中包含一个整数，表示最少需要携带的多少质量的气筒来完成改任务）。

【样例输入】

ple.in

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

【样例输出】

ple.out

249

上次修改时间 2017-02-03