第9章 動(dòng)態(tài)規(guī)劃(背包問題)

1、PASCAL語言語言基礎(chǔ)算法基礎(chǔ)算法第一課時(shí)v8 8、裝載問題、裝載問題v【問題描述】【問題描述】v 有一批共n個(gè)集裝箱要裝上艘載重量為c的輪船，其中集裝箱i的重量為wi。找出一種最優(yōu)裝載方案，將輪船盡可能裝滿，即在裝載體積不受限制的情況下，將盡可能重的集裝箱裝上輪船。v【輸入格式】【輸入格式】v 由文件load.in給出輸入數(shù)據(jù)。第一行有2個(gè)正整數(shù)n和c。n是集裝箱數(shù)，c是輪船的載重量。接下來的1行中有n個(gè)正整數(shù)，表示集裝箱的重量。v【輸出格式】【輸出格式】v 將計(jì)算出的最大裝載重量輸出到文件load.out。v【輸入樣例】【輸入樣例】v5 10v7 2 6 5 4v【輸出樣例】【輸出樣例】

2、v10但是，不論我們?cè)趺从盟阉骰厮菟惴ǖ?，不論我們?cè)趺从盟阉骰厮菟惴ㄗ?，都不能得滿分。那么用什么算法做，都不能得滿分。那么用什么算法做呢？做呢？0/1背包v0 放 1 不放f012345678910000000000007 7 7 7F10:=2+f10-2v再是2 F9:=2+f9-2F8:=2+f8-2 27 先是7 F7:=2+f7-2 270/1背包v0 放 1 不放f01234567891000222227799v再是5 再是6 0/1背包v0 放 1 不放f01234567891000222267799 再是4 【程序】vvar n,c,i,j:longint;v w,f:arr

3、ay0.100000of longint;vBEGINv assign(input,load.in);reset(input);v assign(output,load.out);rewrite(output);v read(n,c);v for i:=1 to n do read(wi);v for i:=1 to n dov for j:= c downto wi dov if fjmax)and(sumn then exitv else for ii:=0 to 1 dov if ii*wk+sum=c thenv search(k+1,sum+wk*ii);v end;vvar n,c

4、,i,j:longint;v w,f:array0.100000of longint;vBEGINv assign(input,load.in);reset(input);v assign(output,load.out);rewrite(output);v read(n,c);v for i:=1 to n do read(wi);v for i:=1 to n dov for j:= c downto wi dov if fjwi+fj-wi thenv fj:=wi+fj-wi;v writeln(fc);前后對(duì)比前后對(duì)比vBEGINv assign(input,load.in);res

5、et(input);v assign(output,load.out);rewrite(output);v read(n,c);v for i:=1 to n do read(wi);v max:=0;v search(1,0);v writeln(max);v CLOSE(INPUT);v CLOSE(OUTPUT);vEND.vCLOSE(INPUT);vCLOSE(OUTPUT); vEND.前后對(duì)比前后對(duì)比想想看，01背包和回溯算法哪個(gè)好？好在哪兒？ 上機(jī)練習(xí)vP268v2.裝箱問題v有一個(gè)箱子容量為v（正整數(shù)，小于等于20000），同時(shí)有n個(gè)物品p1-pn。v要求從n個(gè)物品中，任取m

6、個(gè)裝入箱內(nèi)，使它的剩余空間最少。v輸入格式vVvNvN行。分別表示piv輸出格式v箱子的剩余空間 上機(jī)練習(xí)vP268v2.裝箱問題v輸入樣例boxes.in 輸出樣例boxes.outv24 0v6v8v3v12v7v9v7 上機(jī)練習(xí)vP268v2.裝箱問題v有一個(gè)箱子容量為v（正整數(shù)，小于等于20000），同時(shí)有n個(gè)物品p1-pn。v要求從n個(gè)物品中，任取m個(gè)裝入箱內(nèi)，使它的剩余空間最少。Load.pasvvar n,c,i,j:longint;v w,f:array0.100000of longint;vBEGINv assign(input,load.in);reset(input);v

7、 assign(output,load.out);rewrite(output);v read(n,c);v for i:=1 to n do read(wi);v for i:=1 to n dov for j:= c downto wi dov if fjwi+fj-wi thenv fj:=wi+fj-wi;v writeln(fc);v CLOSE(INPUT);v CLOSE(OUTPUT);vEND.Boxes.pasvvar v,n,i,j:longint;v w,f:array0.100000of longint;vbeginv assign(input,boxes.in);r

8、eset(input);v assign(output,boxes.out);rewrite(output);v readln(v);v readln(n);v for i:=1 to n dov readln(wi);v for i:=1 to n dovfor j:=v downto wi dov if fjwi+fj-wi thenv fj:=wi+fj-wi;v writeln(v-fv);v close(input);v close(output);vend.第二課時(shí)練習(xí)vP268 1.weight.pas分析f0 1 2 3 4 5 6 7 8 1000T F F F F F F

9、F F F參考程序vconst n=6;v b:array1.6of longint=(1,2,3,5,10,20);vvar i,j,k,w,total:longint;v p:array1.6of longint;v f:array0.1000of boolean;vbeginv assign(input,weight.in);reset(INPUT);v assign(output,weight.out);rewrite(output);v for i:=1 to n do read(pi);v w:=0;v f0:=true;v for i:=1 to n dov for j:=1 t

10、o pi dov beginv for k:=w downto 0 dov if fk thenv fk+bi:=true;v w:=w+bi;v end;vfor i:=1 to w dov if fi then inc(total);v writeln(Total=,total);v close(input);v close(output);vend.完全背包vP270 4.開心的金明 happy.pas完全背包vP270 4.開心的金明 happy.pas完全背包vP270 4.開心的金明 happy.pas完全背包vP270 4.開心的金明 happy.pasv分析v其實(shí),完全背包十分

11、簡單,就是把0/1背包倒過來做.f12345678910Happy.pasvvar a,b,c,d,i,j:longint;v f:array0.100000 of longint;vbeginv assign(input,happy.in);reset(input);v assign(output,happy.out);rewrite(output);v readln(a,b);v for i:=1 to b dov beginv readln(c,d);v for j:=a downto c dov if fjfj-c+c*d then fj:=fj-c+c*d;v end;v write

12、(fa);v close(input);close(output);vend.第三課時(shí)P270 5.競賽總分P270 5.競賽總分公式公式：f當(dāng)前時(shí)間當(dāng)前時(shí)間:=f當(dāng)前時(shí)間當(dāng)前時(shí)間-先需用時(shí)間】先需用時(shí)間】+分值；分值；P270 5.競賽總分vvar n,m,x,y,i,j:longint;v f:array0.100000of longint;vbeginv assign(input,inflate.in);reset(input);v assign(output,inflate.out);rewrite(output);v read(n);v read(m);v for i:=1 to m dov beginv read(x,y);v for j:=y to n dov if fj=ai)and(bj0 then bk:=minv else begin inc(w); bw:=ai