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.