本文正體字版由OpenCC轉換

二維費用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