[動態規劃]POI 1998 ple 潛水員問題 解題報告

【問題描述】
     一個潛水員在潛水時使用一種特殊的裝置：一個有兩個容器的氣筒。一個容器中裝的是氧氣，另一個容器中裝氮氣。潛水員需要攜帶的氧氣和氮氣量依賴於潛水的時間和深度。潛水員有一系列的氣筒，用來在不同的情況下攜帶。每個氣筒可以用這樣幾個量來描述：氣筒的質量，氣筒中所能容納的氧氣量，以及可以容納的氮氣量。為了能完成最近的一個任務，潛水員需要一定量的氧氣和氮氣。潛水員有一系列準備好的氣筒。他希望能攜帶總質量儘可能小的氣筒下水。現在請你幫他計算一下至少要攜帶多少質量的氣筒下水才能完成這個任務。

【示例說明】
潛水員有以下 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

【分析】
二維背包～具體方法請看dd的《背包九講》。

【我的代碼】
裸代碼RawCode

C++语言: Codee#25584

001 /*
002 *Problem: POI 1998  ple
003 *Author: Yee-fan Zhu
004 *GTalk: zyfworks@gmail.com
005 *Method: Dynamic Programming
006 */
007 #include <iostream>
008 #include <cstdio>
009 #include <cstdlib>
010 using namespace std;
011 int N;
012 class PLE
013 {
014 public:
015     int O;//Oxygen  酸素
016     int N;//Netrogen 窒素
017     int W;//Weight
018 }P[1001];
019 int T,A;
020 int F[1001][50][160];/*對於前i個氧氣瓶,O2=j,N2=k時的最小質量*/
021
022 const int INF=1000000000;
023 int MIN(int a,int b)
024 {
025     return (a>b?b:a);
026 }
027
028 int MAX(int a,int b)
029 {
030     return (a>b?a:b);
031 }
032
033 int MaxO=0,MaxN=0;
034
035 void init()
036 {
037     scanf("%d %d\n%d\n",&T,&A,&N);
038     for (int i=1;i<=N;i++)
039     {
040         scanf("%d %d %d\n",&P[i].O,&P[i].N,&P[i].W);
041         MaxO=MAX(MaxO,P[i].O);
042         MaxN=MAX(MaxN,P[i].N);
043     }
044     for (int i=1;i<=N;i++)
045     {
046         for(int j=0;j<=T+MaxO;j++)
047             for(int k=0;k<=A+MaxN;k++)
048                 F[i][j][k]=INF;   
049         F[i][0][0]=0;   
050     }
051     return;
052 }
053
054 void dynamic()
055 {
056     for(int k=1;k<=N;k++)
057     {
058         for (int i=1;i<=P[k].O;i++)
059             for (int j=1;j<=P[k].N;j++)
060                 F[k][i][j]=P[k].W;
061     }
062    
063     for(int k=1;k<=N;k++)
064     {
065         for(int i=1;i<=P[k].O;i++)
066             F[k][i][0]=P[k].W;
067         for(int i=1;i<=P[k].N;i++)
068             F[k][0][i]=P[k].W;
069     }
070    
071     int i=2;   
072     for (;i<=N;i++)
073     {
074         for (int j=0;j<=T+MaxO;j++)
075         {
076             for(int k=0;k<=A+MaxN;k++)
077             {
078                 int Min=F[i-1][j][k];
079                 if(j-P[i].O>=0 && k-P[i].N>=0)
080                     Min=MIN(Min,F[i-1][j-P[i].O][k-P[i].N]+P[i].W);
081                 if(j-P[i].O<=0 && k-P[i].N<=0)
082                     Min=MIN(Min,P[i].W);
083                 if(j-P[i].O>=0 && k-P[i].N<=0)
084                     Min=MIN(Min,F[i-1][j-P[i].O][k]+P[i].W);
085                 if(j-P[i].O<=0 && k-P[i].N>=0)
086                     Min=MIN(Min,F[i-1][j][k-P[i].N]+P[i].W);
087                 F[i][j][k]=Min;
088             }
089         }
090     }
091    
092     int Ans=INF;
093     for (int i=T;i<=T+MaxO;i++)
094         for (int j=A;j<=A+MaxN;j++)
095             Ans=MIN(Ans,F[N][i][j]);
096     printf("%d\n",Ans);
097 }
098
099 int main()
100 {
101     freopen("ple.in","r",stdin);
102     freopen("ple.out","w",stdout);
103     init();
104     dynamic();
105     return 0;
106 }