DP 之 SPOJ SCUBADIV (三维 01背包变形)

题目地址：http://www.spoj.com/problems/SCUBADIV/

为更好的解决这个题目，首先应对二维01背包有一定了解，推荐题目： hdu 2602 （友情提醒：界面有点小恐怖，但是一道二维01背包入门题）

/*
定义： dp[i][j][k] := 取前 i 个物品， 所能获得氧气体积（至少）为 j, 氮气（至少）体积为 k, 所需的最小重量
（1）初始化条件： dp[0][0][0] = 0, dp[0][j][k] (k || j != 0) = INF （INF：代表不存在这种情况）
（2）dp[i+1][j][k] = min(dp[i][j][k], dp[i][j-arrT[i]][k-arrA[i]] + arrW[i])
关键：	
	由于所要获得氧气体积为 j, 氮气体积为 k，可大于等于，却决不能小于，
	所以对于 j-arrT[i] < 0 或 k-arrA[i] < 0, 直接取 0 ，可保证这一条件。
	(此处，是与二维标准01背包的区别所在：
			二维标准01背包规定“挑出总重量不超过 W 的物品， 以获得价值最大值”
			而此题要求“氧气体积至少为 j, 氮气体积至少为 k， 以获得最小重量”
			故对于 j-arrT[i] < 0 或 k-arrA[i] < 0 的情况，
			如果令 
			dp[i + 1][j][k] = min(dp[i][j][k], arrW[i] + dp[i][0][0]);
			或 dp[i + 1][j][k] = min(dp[i][j][k], arrW[i] + dp[i][0][k - arrA[i]]);
			或 dp[i + 1][j][k] = min(dp[i][j][k], arrW[i] + dp[i][j - arrT[i]][0])，
			虽然在此时实际所获得氧气体积, 氮气体积已经大于 j 或 k, 
			但仍分析可知仍满足题目要求，可与 dp[i][j][k] 进行比较，选出最小值。
	)
下面有两个代码，第一个代码有助理解，第二个是优化代码，效率以及空间均较优于第一个代码。
*/

第一个代码：

//  [3/29/2014 Sjm]
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 1000, MAX_T = 21, MAX_A = 79, INF = 0x3f3f3f3f;
int c, t, a, n, arrT[MAX_N], arrA[MAX_N], arrW[MAX_N], dp[MAX_N + 1][MAX_T + 1][MAX_A + 1];

int Solve()
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= t; j++)
            for (int k = 0; k <= a; k++)
            {
                // 所要获得氧气体积为 j >= arrT[i] && 氮气体积 k >= arrA[i]
                if (arrT[i] <= j && arrA[i] <= k) {
                    dp[i + 1][j][k] = min(dp[i][j][k], arrW[i] + dp[i][j - arrT[i]][k - arrA[i]]);
                }
                else {
                    // 所要获得氧气体积为 j < arrT[i] && 氮气体积 k < arrA[i]
                    if (arrT[i] > j && arrA[i] > k)
                        dp[i + 1][j][k] = min(dp[i][j][k], arrW[i] + dp[i][0][0]);
                    else{
                        // 仅所要获得氧气体积为 j < arrT[i] 
                        if (arrT[i] > j) {
                            dp[i + 1][j][k] = min(dp[i][j][k], arrW[i] + dp[i][0][k - arrA[i]]);
                        }
                        // 仅所要获得氮气体积 k < arrA[i]
                        else {
                            dp[i + 1][j][k] = min(dp[i][j][k], arrW[i] + dp[i][j - arrT[i]][0]);
                        }
                    }
                }
            }
    }
    return dp[n][t][a];
}

int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d", &c);
    while (c--)
    {
        scanf("%d%d%d", &t, &a, &n);
        for (int i = 0; i < n; i++)
            scanf("%d%d%d", &arrT[i], &arrA[i], &arrW[i]);
        for (int i = 0; i <= t; i++)
            for (int j = 0; j <= a; j++){
                dp[0][i][j] = INF;
            }
        dp[0][0][0] = 0;
        printf("%d
", Solve());
    }
    return 0;
}

第二个优化代码：

//  [3/29/2014 Sjm]
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 1000, MAX_T = 21, MAX_A = 79, INF = 0x3f3f3f3f;
int c, t, a, n, arrT[MAX_N], arrA[MAX_N], arrW[MAX_N], dp[2][MAX_T + 1][MAX_A + 1];

int Solve()
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= t; j++)
            for (int k = 0; k <= a; k++)
                dp[(i + 1) % 2][j][k] = min(dp[i % 2][j][k], arrW[i] + dp[i % 2][max(0, j - arrT[i])][max(0, k - arrA[i])]);
    }
    return dp[n % 2][t][a];
}

int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d", &c);
    while (c--)
    {
        scanf("%d%d%d", &t, &a, &n);
        for (int i = 0; i < n; i++)
            scanf("%d%d%d", &arrT[i], &arrA[i], &arrW[i]);
        for (int i = 0; i <= t; i++)
            for (int j = 0; j <= a; j++){
                dp[0][i][j] = INF;
            }
        dp[0][0][0] = 0;
        printf("%d
", Solve());
    }
    return 0;
}