改后为w[i] to m,自然没这个问题了
还是有很多问题
因为如果出现 w[i]=0,若 value[i] <= 0 则物品无用,但是如果 value[i] > 0 那么最后的答案就是无限,但是在这样的背包程序中仍然只会被加一次(注意 j-w[0]=j),那么我们完全可以怀疑数据有问题
看来可能需要renqing或者binarie检查一下数据正确与否
测试结果1: 通过本测试点|有效耗时235:ms
测试结果2: 通过本测试点|有效耗时172:ms
测试结果3: 通过本测试点|有效耗时312:ms
测试结果4: 测试结果错误.错误结果为:*16950743
正确结果应为:16950743
测试结果5: 通过本测试点|有效耗时281:ms
测试结果6: 测试结果错误.错误结果为:*95059634
正确结果应为:95068146
测试结果7: 测试结果错误.错误结果为:*11129877
正确结果应为:11144826
测试结果8: 通过本测试点|有效耗时219:ms
测试结果9: 测试结果错误.错误结果为:*6448191
正确结果应为:6450430
测试结果10: 通过本测试点|有效耗时234:ms
提交代码: var n,m,i,j:longint;
w,v,f:array[0..10001]of longint;
begin
readln(n,m);
for i:=1 to n do
begin
readln(w[i],v[i]);
if w[i]=0 then
begin
if v[i]=0 then write(’$’) else write(’*’)
end;
end;
for i:=1 to m do f[i]:=-maxlongint;
for i:=1 to n do
begin
f[0]:=0;
for j:=1 to m do
if (j>=w[i]) and (f[j-w[i]]+v[i]>f[j]) then f[j]:=f[j-w[i]]+v[i];
end;
writeln(f[m]);
end.
我用小号cheat了一下数据,的却有W[I]=0而V[I]<>0的情况,但是我第4个点为什么还能过??(除去*)
3 7
3/2
2/100
4/2
完全有可能是3+2+2价值202.
我觉得
3 7
3/2
5/100
4/2
更能反映你的意思,你说呢?