0/1背包問題，和624類似，只是這次價(jià)值和花費(fèi)不同，這次同樣需要輸出選擇的物品。
輸出惡心到我了，竟然PE兩次。
#include <stdio.h>
#include <string.h>
#define T 1005
#define N 35
struct Treature
{
int depth, time, value;
}treature[N];
int c[T];
bool p[N][T];
int main()
{
int t, w, n, count, cas = 0;
while(~scanf("%d %d", &t, &w))
{
if(cas) puts("");
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
int depth, value;
scanf("%d %d", &depth, &value);
treature[i].depth = depth;
treature[i].time = 3 * depth * w;
treature[i].value = value;
}
memset(c, 0, sizeof(c));
memset(p, 0, sizeof(p));
for(int i = n; i; i--)
for(int j = t; j >= treature[i].time; j--)
{
if(c[j] < c[j - treature[i].time] + treature[i].value)
{
c[j] = c[j - treature[i].time] + treature[i].value;
p[i][j] = 1;
}
}
printf("%d\n", c[t]);
count = 0;
for(int i = 1, j = t; i <= n; i++)
if(p[i][j])
{
count++;
j -= treature[i].time;
}
printf("%d\n", count);
for(int i = 1, j = t; i <= n; i++)
if(p[i][j])
{
printf("%d %d\n", treature[i].depth, treature[i].value);
j -= treature[i].time;
}
cas++;
}
return 0;
}