【題解】UVA 00990 Diving for Gold

【題目敘述】https://vjudge.net/problem/UVA-990
【解題想法】DP,01背包,需印出得到最佳解的方法。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
//dp[i][j]: 第i個寶藏在“時間j”時是否拿取
//dp 紀錄了獲取最大價值的軌跡
bool dp[35][1005];
//val[i]: 在"時間i"時可獲得的最大價值
int val[1005];
int d[35], v[35]; //讀入測資

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t, w, n;
    bool first = true;
    while (cin >> t >> w){
        cin >> n;
        for (int i = 0; i < n; i++){
            cin >> d[i] >> v[i];
        }
        memset(dp, false, sizeof(dp));
        memset(val, 0, sizeof(val));
        for (int i = 0; i < n; i++){
            for (int j = t; j >= 0; j--){
                //潛入和上升,共需 wd + 2wd = 3wd 的時間
                int Time = 3 * w * d[i];
                if (j >= Time){
                    if (val[j - Time] + v[i] > val[j]){
                        val[j] = val[j - Time] + v[i];
                        dp[i][j] = true;
                    }
                }
            }
        }
        //總花費時間Time時,可獲得最大價值mx
        int mx = 0, Time = -1;
        for (int i = 0; i <= t; i++){
            if (val[i] > mx){
                mx = val[i];
                Time = i;
            }
        }
        //回溯藉由取得哪些寶藏可累積mx
        vector<int> ans;
        while (Time){
            for (int i = n-1; i >= 0; i--){
                if (dp[i][Time]){
                    ans.push_back(i);
                    Time -= 3 * w * d[i];
                }
            }
        }
        if (first) first = false;
        else cout << "\n";
        cout << mx << "\n";
        cout << ans.size() << "\n";
        //依測資讀入的順序印出
        reverse(ans.begin(), ans.end());
        for (auto i:ans){
            cout << d[i] << " " << v[i] << "\n";
        }
    }
    return 0;
}
分享本文 Share with friends