UVA990 Diving for Gold【0-1背包】

John is a diver and a treasure hunter. He has just found the location of a pirate ship full of treasures. The sofisticated sonar system on board his ship allows him to identify the location, depth and quantity of gold in each suken treasure. Unfortunatelly, John forgot to bring a GPS device and the chances of ever finding this location again are very slim so he has to grab the gold now. To make the situation worse, John has only one compressed air bottle.
    John wants to dive with the compressed air bottle to recover as much gold as possible from the wreck. Write a program John can use to select which treasures he should pick to maximize the quantity of gold recovered.
    The problem has the following restrictions:
• There are n treasures {(d1, v1),(d2, v2), . . .(dn, vn)} represented by the pair (depth, quantity of gold). There are at most 30 treasures.
• The air bottle only allows for t seconds under water. t is at most 1000 seconds.
• In each dive, John can bring the maximum of one treasure at a time.
• The descent time is tdi = w ∗ di, where w is an integer constant.
• The ascent time is tai = 2w ∗ di, where w is an integer constant.
• Due to instrument limitations, all parameters are integer.
Input
The input to this program consists of a sequence of integer values. Input contains several test cases.
The first line of each dataset should contain the values t and w. The second line contains the number
of treasures. Each of the following lines contains the depth di and quantity of gold vi of a different
treasure.
    A blank line separates each test case.
Note:
    In this sample input, the bottle of compressed air has a capacity of 200 seconds, the constant w has the value 4 and there are 3 treasures, the first one at a depth of 10 meters and worth 5 coins of gold, the second one at a depth of 10 meters and worth 1 coin of gold, and the third one at 7 meters and worth 2 coins of gold.
Output
The first line of the output for each dataset should contain the maximum amount of gold that John can recover from the wreck. The second line should contain the number of recovered treasures. Each of the following lines should contain the depth and amount of gold of each recovered treasure. Treasures should be presented in the same order as the input file.
    Print a blank line between outputs for different datasets.
Sample Input
210 4
3
10 5
10 1
7 2
Sample Output
7
2
10 5
7 2

问题链接：UVA990 Diving for Gold
问题简述：一个潜水者去海底寻找金子，已知n个地点有金子，分别给出这些点的深度和价值。由于潜水者只有一瓶氧气，所以他只能在海底呆有限的时间，问如何才能在有限的时间里获得尽可能多的金子，并打印出方案。
问题分析：0-1背包问题。参考链接的解法比较巧妙。
程序说明：（略）
参考链接：UVa 990 - Diving for Gold
题记：（略）

AC的C++语言程序如下：

/* UVA990 Diving for Gold */

#include <bits/stdc++.h>

using namespace std;

const int N = 30 + 1;
int d[N], v[N], dp[N][5000], ans[N];

int main()
{
    int t, w, n, sline = 0;
    while(~scanf("%d%d%d", &t, &w, &n)) {
        for(int i = 1; i <= n; i++)
            scanf("%d%d", &d[i], &v[i]);

        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= t; j++) {
                int tmp = d[i] * w * 3;
                if(j >= tmp)
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - tmp] + v[i]);
                else
                    dp[i][j] = dp[i - 1][j];
            }

        int len = 0;
        for(int i = n, j = t; i >0; i--) {
            int tmp = d[i] * w * 3;
            if(j - tmp >= 0 && dp[i][j] == dp[i - 1][j - tmp]+v[i])
                    ans[len++] = i, 	j -= tmp;
        }

        if(sline++) printf("\n");
        printf("%d\n", dp[n][t]);
        printf("%d\n", len);
        for(int i = len - 1; i >= 0; i--)
            printf("%d %d\n", d[ans[i]], v[ans[i]]);
    }

    return 0;
}