背包习题讲解一.ppt

单击此处编辑母版标题样式 单击此处编辑母版副标题样式 背包习题讲解一 主讲人：山成虎 1.砝码称重 参考程序一： var c,a,f:Array[0..2000]of longint; i,j,k,ans:longint; begin for i:=1 to 6 do read(a[i]); c[1]:=1; c[2]:=2; c[3]:=3; c[4]:=5; c[5]:=10; c[6]:=20; f[0]:=1; for i:=1 to 6 do for j:=1000 downto c[i] do for k:=1 to a[i] do if f[j-k*c[i]]=1 then f[j]:=1; for i:=1 to 1000 do if f[i]=1 then inc(ans); writeln(Total=,ans); end. 参考程序二： var c,a,f:Array[0..2000]of longint; i,j,k,ans:longint; begin for i:=1 to 6 do read(a[i]); c[1]:=1; c[2]:=2; c[3]:=3; c[4]:=5; c[5]:=10; c[6]:=20; f[0]:=1; for i:=1 to 6 do for k:=1 to a[i] do for j:=1000 downto c[i] do if f[j-c[i]]=1 then f[j]:=1; for i:=1 to 1000 do if f[i]=1 then inc(ans); writeln(Total=,ans); end. 2.装箱问题 参考程序： var f:array[0..20000]of boolean; v,m,i,j,o,max:longint; begin readln(v); readln(m); f[0]:=true; for i:=1 to m do begin readln(o); for j:=v downto 0 do if (j+o=v)and(f[j]) then f[j+o]:=true; end; for j:=0 to v do if f[j] then max:=j; writeln(v-max); end. 3.采药 参考程序： var t,m,i,j,c,w,max:longint; f:array[0..100000]of longint; begin readln(t,m); for i:=1 to m do begin readln(w,c); for j:=t downto w do if f[j-w]+cf[j] then f[j]:=f[j-w]+c; end; for i:=1 to t do if maxf[i] then max:=f[i]; writeln(max); end. 4.开心的金明 参考程序： var n,m,w,c,i,j:longint; f:array[0..100000]of longint; begin readln(n,m); for i:=1 to m do begin readln(w,c); c:=c*w; for j:= n downto w do if f[j-w]+cf[j] then f[j]:=f[j-w]+c; end; for i:=2 to n do if f[i]f[1] then f[1]:=f[i]; writeln(f[1]); end. 5.竞赛总分 参考程序： var m,n,w,u,i,j:longint; f:Array[0..100000]of longint; begin readln(m,n); for i:=1 to n do begin readln(w,u); for j:=u to m do if f[j-u]+wf[j] then f[j]:=f[j-u]+w; end; for j:=1 to m do if f[j]f[0] then f[0]:=f[j]; writeln(f[0]); end. 6.最小乘车费用 参考程序： program p1044; var