【題解】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;
}
```