marslove 2008-04-20 19:59:00
点我顶贴
收藏
删除
这样搜索有错吗?难道非要背包做?
var i,j,n,m,s,d:longint；
a,b,c:array [1..10000] of longint；
begin
s:=0；
d:=0；
readln (n,m)；
for i:=1 to m do
begin
read (a[i])；
readln (b[i])；
end；
for i:=1 to m do
c[i]:=a[i]*b[i]；
while n>=0 do
begin
j:=0；
for i:=1 to m do
if (c[i]>j) and (a[i]<=n) then begin j:=c[i]；d:=i； end；
c[d]:=0；
n:=n-a[d]；
s:=s+j；
end；
write(s)；
end.
#2 烽火连城@2008-04-20 19:59:00
1310
回复
删除
--------
for i:=1 to m do
if (c[i]>j) and (a[i]<=n) then begin j:=c[i]；d:=i； end；
c[d]:=0；
n:=n-a[d]；
s:=s+j；
end；
----------这个程序段是从第一个到第Ｍ个来比较，如果比Ｎ小就买，但是你看测试数据，第一个800块，重要度２，这个按你的程序是符合条件的，但实际上不是．
我的考虑是把 钱数/重要度 得出一个每重要度的钱数，先考虑最小的，比如 800 2 和 500 3 就应该先选择买500的东西，