题目大意：一个潜水者去海底寻找金子，已知有n个有金子的地点，分别给出他们的深度和价值。但是由于潜水者只有一瓶氧气，所以他只能在海底呆有限的时间，问他如何才能在这有限的时间里获得尽可能多的金子，并打印出方案。
dp中的0-1背包问题，得到最大值后根据dp数组可得到解决方案。采用“后i个物品”的规划方向可以使打印方案变得简单一点，详见《算法竞赛入门经典》9.3节。
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std; int d[], v[], dp[][];
vector<int> ans; int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int time, w;
bool first = true;
while (scanf("%d%d", &time, &w) != EOF)
{
int k = time / (*w);
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d%d", &d[i], &v[i]);
for (int i = ; i <= k; i++)
dp[n+][i] = ;
for (int i = n; i > ; i--)
for (int j = ; j <= k; j++)
{
dp[i][j] = dp[i+][j];
if (j >= d[i] && dp[i+][j-d[i]]+v[i] > dp[i][j])
dp[i][j] = dp[i+][j-d[i]]+v[i];
}
if (first) first = false;
else printf("\n");
printf("%d\n", dp[][k]);
ans.clear();
for (int i = , j = k; i <= n; i++)
if (j >= d[i] && dp[i][j] == dp[i+][j-d[i]]+v[i])
{
ans.push_back(i);
j -= d[i];
}
cout << ans.size() << endl;
for (int i = ; i < ans.size(); i++)
{
int idx = ans[i];
printf("%d %d\n", d[idx], v[idx]);
}
}
return ;
}