讨论 / WA70 求纠错
shengyangweb 2011-08-15 06:44:00
点我顶贴 收藏 删除
就是0/1背包+输出方案,应该没错啊

Program QingGongHui;

Var c,w:array[0..500] of longint;

f:array[0..500,0..5000] of longint;

flag:array[1..500] of boolean;

i,j,k,s,m,n,t,sum:longint;

Function Max(x,y:longint):longint;

begin

if x>y then exit(x);

exit(y);

end;

Procedure Dfs(i,j,s:longint);

var k:longint;

begin

if s=f[n,m] then

begin

for k:=1 to n do

if flag[k] then write(k,' ');

halt;

end;

if f[i,j]=f[i-1,j-c[i]]+w[i] then

begin

flag[i]:=true;

Dfs(i-1,j-c[i],s+w[i]);

end

else Dfs(i-1,j,s);

end;

Begin

fillchar(flag,sizeof(flag),0);

readln(n,m);

for i:=1 to n do

begin

readln(j,k,s);

c[i]:=j*s;

w[i]:=k*s;

end;

for i:=1 to n do

for j:=0 to m do

if j>=c[i] then

f[i,j]:=max(f[i-1,j-c[i]]+w[i],f[i-1,j])

else f[i,j]:=f[i-1,j];

writeln(f[n,m]);

Dfs(n,m,0);

End.

#1 ahfy_zyt@2011-08-15 06:44:00
回复 删除
我也是WA70,请指教

program qgh;

var

a:array [0..500,1..5000] of longint;

v,w:array [1..500] of longint;

n,m,s:longint;

i,j,k:longint;

function max(a,b:longint):longint;

begin

if a>b then max:=a else max:=b;

end;

procedure find(d,t:longint);

begin

if d=0 then exit;

if a[d-1,t-v[d]]+w[d]=a[d,t] then

begin

find(d-1,t-v[d]);

write(d,' ');

end

else find(d-1,t);

end;

begin

readln(n,m);

for i:=1 to n do

begin

readln(v[i],w[i],s);

v[i]:=v[i]*s;

w[i]:=w[i]*s;

end;

fillchar(a,sizeof(a),0);

for i:=1 to n do

for j:=1 to m do

if (j>=v[i]) then

begin

a[i,j]:=max(a[i-1,j],a[i-1,j-v[i]]+w[i]);

end

else

a[i,j]:=a[i-1,j];

writeln(a[n,m]);

find(n,m);

readln;

end.

状态: Unaccepted

测评机: Xeost[5]

得分: 0分

提交日期: 2011-8-15 21:35:00

有效耗时: 1298毫秒

测试结果1: 通过本测试点|有效耗时172ms

测试结果2: 测试结果错误.错误结果为:70701

5 18 40 42 45 48 60 79 83 84 90 92 103 105 109 112 120 133 154 171 175 191 196 214 218 225 227 238 241 247 251 259 273 280 293 304

正确结果应为:70701

5 18 42 45 48 60 90 92 105 109 120 133 154 171 175 191 196 214 218 225 227 238 241 259 273 293 304

测试结果3: 通过本测试点|有效耗时172ms

测试结果4: 通过本测试点|有效耗时188ms

测试结果5: 通过本测试点|有效耗时172ms

测试结果6: 测试结果错误.错误结果为:137034

13 14 15 17 24 28 34 49 52 56 59 65 77 85 88 97 98 101 102 110 121 126 127 130 140 141 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

测试结果7: 通过本测试点|有效耗时172ms

测试结果8: 通过本测试点|有效耗时188ms

测试结果9: 测试结果错误.错误结果为:100892

5 9 19 28 33 34 35 37 45 47 57 72 74 81 86 90 91 100 102 119 120 122 125 127 128 130 137 138 140 144 145 147 148 154 161 162 173 181 186 188 191 203 204 211

正确结果应为:100892

5 9 19 28 33 34 35 37 45 47 57 72 91 100 102 119 120 122 128 130 137 138 140 144 145 147 148 154 161 162 173 181 186 188 191 203 204 211

测试结果10: 通过本测试点|有效耗时234ms

查看更多回复
提交回复