讨论 / 大牛帮忙看一下My program
wx--168 2008-06-27 23:00:00
点我顶贴 收藏 删除
大牛帮忙看一下,三个点没过……

测试结果1: 测试结果正确

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

正确结果应为:9651

测试结果3: 测试结果错误.错误结果为:12378

正确结果应为:11488

测试结果4: 测试结果错误.错误结果为:19864

正确结果应为:18382

测试结果5: 测试结果正确

测试结果6: 测试结果正确

测试结果7: 测试结果正确

测试结果8: 测试结果正确

测试结果9: 测试结果正确

测试结果10: 测试结果正确

提交代码:

program wx;

var i,j,k,m,n,v,w,s,t,x:longint;

a:array[0..500]of longint;

begin

readln(n,v);

for i:=1 to n do

begin

readln(m,w,s);

t:=trunc(ln(m)/ln(2))+1;

x:=1;

for k:=1 to t do

begin

for j:=v downto w*x do

if a[j-w*x]+s*x>a[j] then

a[j]:=a[j-w*x]+s*x;

x:=2*x;

if k=t-1 then x:=m-x div 2;

end;

end;

writeln(a[v]);

end.

#1 nestman@2008-06-27 22:33:00
回复 删除
我不知道...我打算把它变为完全背包(两者关系好像更进一些。
#2 nestman@2008-06-27 22:38:00
回复 删除
不管了...尝试一下!
#3 caoyuan9642@2008-06-27 23:00:00
回复 删除
不用O(nlogn);

直接加一重循环

枚举数量

只不过是O(n*(各物品数量的和))

查看更多回复
提交回复