WA掉了，输出的价值一样，种类序号不同，但是看本人程序最后几行......他wa了，没TLE，大家懂的.........

#include <cstdio>

#include <algorithm>

int n,m;

int f[505][5005],ans[505],w[505],v[505],num[505];

bool choose[505][5005];

int main() {

freopen("1.in","r",stdin);

scanf("%d%d", &n, &m);

for (int i = 1;i <= n;i++) {

scanf("%d%d%d", &w[i], &v[i], &num[i]);

w[i] *= num[i],v[i] *= num[i];

for (int j = 0;j <= w[i];j++) f[i][j] = f[i - 1][j];

for (int j = w[i];j <= m;j++) {

if (f[i - 1][j] > f[i - 1][j - w[i]] + v[i]) {

f[i][j] = f[i - 1][j],choose[i][j] = 0;

} else {

f[i][j] = f[i - 1][j - w[i]] + v[i],choose[i][j] = 1;

}

}

}

printf("%d\n", f[n][m]);

int k = m;

for (int i = n;i >= 1;i--)

if (choose[i][k]) {

k -= w[i];

ans[++ans[0]] = i;

}

for (int i = ans[0];i >= 1;i--) printf("%d ", ans[i]);

printf("\n");

int tmp = 0;

for (int i = 1;i <= ans[0];i++) tmp += v[ans[i]];

if (tmp != f[n][m]) while(1);

return 0;

}

回复 楼主狼人墓地 的帖子

额，忽略那个freopen。。。T_T.....