[动态规划练习题]潜水

【问题描述】
潜水员用特殊的装备潜水，需要两个容器的钢瓶：一个装氧气，另一个装氮气。根据潜水员要待在水下的时间和所潜的深度，他需要不同量的氧气和氮气。提供给潜水员一定数量的钢瓶，每个钢瓶由它的重量和它所容纳的气体的体积描述。为了完成任务，潜水员需要特定量的氧气和氮气，需要求他完成任务所需的钢瓶的最少重量是多少？
例如，潜水员能够使用的5个钢瓶描述如下，每个描述包含：氧气的体积，氮气的体积（每个值都是以升为单位）和钢瓶的重量。
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
如果潜水员需要5升氧气和60升氮气，那么他必须带两个总重量为249的钢瓶（例子中的第1与第2或者第4与第5）。

【任务】
读入潜水员的氧气和氮气的需求量，提供的钢瓶的数目及它们的描述；
计算潜水员完成任务所需要的钢瓶最少重量；
注：提供的钢瓶总能够完成给定的任务。 
   
【输入格式】
第一行有两个整数T，A，它们由空格隔开，1≤T≤100，1≤A≤100，它们分别表示氧气的体积和氮气的体积，这些是完成任务需要的。第二行有一个整数N，1≤N≤1000，表示提供钢瓶的总数量，接下来的N行是对每个钢瓶的描述，第I+2行包含3个整数，TI，AI，WI，它们由空格隔开，其中1≤TI≤100，1≤AI≤100，1≤WI≤800；它们分别表示第I个钢瓶内氧气的体积、氮气的体积以及该钢瓶的重量，1≤I≤N。  

【输出格式】
输出只有一个整数，就是潜水员完成任务所需钢瓶的最少总重量。 

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

【样例输出】
249

【时间限制】
每个测试点1s。

【解析】

• 状态：f[j][k]表示氧气为j，氮气为k时的钢瓶最小重量
• 状态转移方程：f[j+t[i]][k+a[i]] = min(f[j+t[i]][k+a[i]], f[j][k]+c[i])
• 答案：f[T][A]
• 时间复杂度：O(N*T*A)

[cpp]#include <cstdio>
int T, A, N, f[200][200], t[1020], a[1020], v[1020];
int main(void)
{
    scanf(“%d%d%d”, &T, &A, &N);
    for (int i=1; i<=N; ++i)
        scanf(“%d%d%d”, &t[i], &a[i], &v[i]);
    for (int i=0; i<=T; ++i)
        for (int j=0; j<=A; ++j)
            f[i][j]=10000000;
    f[0][0]=0;
    for (int i=1; i<=N; ++i)
        for (int j=T; j>=0; –j)
            for (int k=A; k>=0; –k)
            {
                int o1, o2;
                if (t[i]+j > T)
                    o1=T;
                else
                    o1=t[i]+j;
                if (a[i]+k > A)
                    o2=A;
                else
                    o2=a[i]+k;
                if (f[o1][o2]>f[j][k]+v[i])
                    f[o1][o2]=f[j][k]+v[i];
            }
    printf(“%d\n”, f[T][A]);

    return 0;
}

[/cpp]