考试时觉得挺难,看了题解觉得晕,在做是很轻松就AC了

我觉得我的方法挺简单,帖出来与大家分享,不要BS我噢!

program gf

const

maxn=110

var

rmb,rp,time:array[0..maxn] of longint

opt,ct:array[0..maxn,0..maxn] of longint

n,m,r,ans,max:longint

procedure init

var

i:longint

begin

read(n)

for i:=1 to n do

read(rmb[i],rp[i],time[i])

read(m,r)

end

procedure main

var

i,j,k:longint

begin

fillchar(opt,sizeof(opt),0)

fillchar(ct,sizeof(ct),0)

opt[0,0]:=1

for i:=1 to n do

for j:=m downto rmb[i] do

for k:=r downto rp[i] do

if opt[j-rmb[i],k-rp[i]]>0 then

begin

if opt[j-rmb[i],k-rp[i]]+1>opt[j,k] then

begin

opt[j,k]:=opt[j-rmb[i],k-rp[i]]+1

ct[j,k]:=ct[j-rmb[i],k-rp[i]]+time[i]

end

else if (opt[j-rmb[i],k-rp[i]]+1=opt[j,k])

and (ct[j-rmb[i],k-rp[i]]+time[i]<ct[j,k]) then

ct[j,k]:=ct[j-rmb[i],k-rp[i]]+time[i]

end

max:=0

for j:=1 to m do

for k:=1 to r do

if opt[j,k]>max then

begin

max:=opt[j,k]

ans:=ct[j,k]

end

else if (opt[j,k]=max) and (ct[j,k]<ans) then

ans:=ct[j,k]

end

procedure print

begin

writeln(ans)

end

begin

init

main

print

end.

想要解题报告的可以找我.

QQ:526226722

咳咳

大牛

报告给我一份吧

呵呵赵剑波你这小子的和我的差不多...

program gf

var

f,g:array[0..100,0..100] of longint

n,i,j,k,m,s,r,time:longint

a,b,c:array[1..100] of longint

begin

read(n)

for i:=1 to n do

read(a[i],b[i],c[i])

fillchar(f,sizeof(f),0)

fillchar(g,sizeof(g),0)

read(m,r)

for i:=1 to n do

for j:=m downto a[i] do

for k:=r downto b[i] do

begin

if f[j,k]=f[j-a[i],k-b[i]]+1 then

if g[j,k]>g[j-a[i],k-b[i]]+c[i] then

g[j,k]:=g[j-a[i],k-b[i]]+c[i]

if f[j,k]<f[j-a[i],k-b[i]]+1 then

begin

f[j,k]:=f[j-a[i],k-b[i]]+1

g[j,k]:=g[j-a[i],k-b[i]]+c[i]

end

end

write(g[m,r])

end.

呵呵....

给我发题解嘛，[email protected] 谢谢了

这题菜鸟我都过了……

为什么把循环的顺序倒过来就会错？？

因为用的是二维背包g[j,k]:=g[j-a[i],k-b[i]]+c[i]

而不是g[i,j,k]:=g[i-1,j-a[i],k-b[i]]+c[i]

缩小一维的话要从上往下DP才不至于被刚做的就被替换了

如果从下往上DP的话刚做的就会被搜索到，达不到i与i-1的比较

水

for i:=1 to n do

for p:=m downto tmb[i] do

for q:=k downto rp[i] do

if f[p-tmb[i],q-rp[i]]+c[i]>f[p,q]

then f[p,q]:=f[p-tmb[i],q-rp[i]]+c[i];

核心烂代码