Question

庆功会 一道01背包的路径输出问题

八（1）班由于在期中考中获得了团体第一名，班主任吴老师决定开一场庆功会。于是购买东西的任务就交给了小李同学（钱由班会出）。由于小李同学四肢发达，头脑简单，于是这个任务便落到了你头上（当然不要你跑腿。跑腿是小李的事 ^_^）
注：可以全买，但不能不买。即至少买1种

输入格式
第一行二个数n(n<=500)，m(m<=5000)，其中n代表希望购买的物品的种数，m表示班会拨给小李的钱数。
接下来n行，每行3个数，v、w、s，分别表示第I种物品的价格、价值（价格 与 价值 是不同的概念）和购买的数量（只能买0件或s件），其中v<=100,w<=1000,s<=10

输出格式
共两行：
第一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。
第二行：小李此次购买（能获得的最大价值）所选择的物品种类的序号。
var i,j,s,m,n:longint;
f:array[0..10000] of longint;
last:array[0..500,0..10000] of longint;
v,w:array[0..10000] of longint;
b:array[0..500] of boolean;
procedure huisu(i,j:longint);
begin
if j<>0 then
begin
if last[i,j]=j-v[i] then b[i]:=true;
huisu(i-1,last[i,j]);
end;
end;
begin
readln(n,m);
fillchar(b,sizeof(b),false);
for i:=1 to n do
begin
readln(v[i],w[i],s);
v[i]:=v[i]*s;
w[i]:=w[i]*s;
end;
f[0]:=0;
for i:=1 to n do
for j:=m downto v[i] do
begin
if f[j-v[i]]+w[i]>f[j] then
begin
f[j]:=f[j-v[i]]+w[i];
last[i,j]:=j-v[i];
end else last[i,j]:=j;
end;
writeln(f[m]);
huisu(n,m);
for i:=1 to n do if b[i] then write(i,' ');
end.

看看这个程序哪里不对..

测试结果错误.错误结果为:113354
51 58 63 68 71 73 83 90 97 110 114 116 119 122 130 137 145 147 148 150 165 167 170 172 173 176 179 181 186 188 190 194 198 200 208 215
正确结果应为:113354
7 22 28 38 41 46 51 58 63 68 71 73 83 90 97 110 114 116 119 122 130 137 145 147 148 150 165 167 170 172 173 176 179 181 186 188 190 194 198 200 208 215

测试结果错误.错误结果为:137034
145 150 158 162 173 174 181 182 184 187 202 204 205 208 219 221 226 238 244 245 246 251 253 256 278 285
正确结果应为:137034
13 14 15 17 24 28 34 49 52 56 59 65 77 85 88 97 98 101 102 110 121 126 130 140 141 145 150 158 162 173 174 181 182 184 187 202 204 205 208 219 221 226 244 245 251 253 256 285

我的两组测试数据 跪求

若以下回答无法解决问题，邀请你更新回答

Answer 1

输入格式
第一行二个数n(n<=500)，m(m<=5000)，其中n代表希望购买的物品的种数，m表示班会拨给小李的钱数。
接下来n行，每行3个数，v、w、s，分别表示第I种物品的价格、价值（价格 与 价值 是不同的概念）和购买的数量（只能买0件或s件），其中v<=100,w<=1000,s<=10

输出格式
共两行：
第一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。
第二行：小李此次购买（能获得的最大价值）所选择的物品种类的序号。
var i,j,s,m,n:longint;
f:array[0..10000] of longint;
last:array[0..500,0..10000] of longint;
v,w:array[0..10000] of longint;
b:array[0..500] of boolean;
procedure huisu(i,j:longint);
begin
if j<>0 then
begin
if last[i,j]=j-v[i] then b[i]:=true;
huisu(i-1,last[i,j]);
end;
end;
begin
readln(n,m);
fillchar(b,sizeof(b),false);
for i:=1 to n do
begin
readln(v[i],w[i],s);
v[i]:=v[i]*s;
w[i]:=w[i]*s;
end;
f[0]:=0;
for i:=1 to n do
for j:=m downto v[i] do
begin
if f[j-v[i]]+w[i]>f[j] then
begin
f[j]:=f[j-v[i]]+w[i];
last[i,j]:=j-v[i];
end else last[i,j]:=j;
end;
writeln(f[m]);
huisu(n,m);
for i:=1 to n do if b[i] then write(i,' ');
end.

看看这个程序哪里不对..

测试结果错误.错误结果为:113354
51 58 63 68 71 73 83 90 97 110 114 116 119 122 130 137 145 147 148 150 165 167 170 172 173 176 179 181 186 188 190 194 198 200 208 215
正确结果应为:113354
7 22 28 38 41 46 51 58 63 68 71 73 83 90 97 110 114 116 119 122 130 137 145 147 148 150 165 167 170 172 173 176 179 181 186 188 190 194 198 200 208 215

测试结果错误.错误结果为:137034
145 150 158 162 173 174 181 182 184 187 202 204 205 208 219 221 226 238 244 245 246 251 253 256 278 285
正确结果应为:137034
13 14 15 17 24 28 34 49 52 56 59 65 77 85 88 97 98 101 102 110 121 126 130 140 141 145 150 158 162 173 174 181 182 184 187 202 204 205 208 219 221 226 244 245 251 253 256 285

我的两组测试数据 跪求