3144046cjc 2008-06-11 04:11:00
点我顶贴
收藏
删除
var tt,i,m,t,a,b:longint;v:array[0..1000] of longint;
begin
readln(t,m);
for i:=1 to m do
begin readln(a,b);
for tt:=t-a downto 0 do if v[tt+a]<v[tt]+b then v[tt+a]:=v[tt]+b;
end;
a:=0;for i:=t downto 1 do if v[i]>max then max:=v[i];writeln(a);
end.
#1 gaoxin@2008-02-10 05:45:00
685
回复
删除
你对01背包还不熟悉,建议看<背包问题九讲>
你的程序循环结束后只要写上writeln(v[t]);就可以了,因为容量最大时价值一定最大
#2 3144046cjc@2008-02-10 06:04:00
688
回复
删除
貌似我以前都是直接写v[t]的,知道有一次俺老师告诉我你这样很容易出错,所以我就加了下面一句,看来还是要相信自己啊,毕竟老师只是师大毕业的。
#5 fjxmlhx@2008-06-11 04:11:00
1832
回复
删除
程序改成一行的最精简了~
var
p:array[0..1000] of longint;
a,b,n,m,i,j:longint;
begin
readln(n,m);
for i:=1 to m do
begin
read(a,b);
for j:=n downto a do
if p[j-a]+b>p[j] then p[j]:=p[j-a]+b;
end;
write(p[n]);
end.