歷屆NOIP搜索算法全集

歷屆NOIP搜索算法全集轉(zhuǎn)自：oifans用動(dòng)態(tài)規(guī)劃來解背包問題在歷屆NOIP競賽中，有4道初賽題和5道復(fù)賽題均涉及到背包問題，所謂的背包問題，可以描述如下：一個(gè)小偷打劫一個(gè)保險(xiǎn)箱，發(fā)現(xiàn)柜子里有N類不同大小與價(jià)值的物品，但小偷只有一個(gè)容積為M的背包來裝東西，背包問題就是要找出一個(gè)小偷選擇所偷物品的組合，以使偷走的物品總價(jià)值最大。如有4件物品，容積分別為：3458對應(yīng)的價(jià)值分別為：45710小偷背包的載重量為：12則取編號(hào)為123的物品，得到最大價(jià)值為16。算法分析：如果采用貪心法，則先取價(jià)值最大的10，消耗了容積8，下面只能取容積為4的物品，得到價(jià)值5，這樣總價(jià)值是15，這不是最優(yōu)解，因此貪心法是不正確的。采用窮舉法，用一個(gè)B數(shù)組來表示取數(shù)的標(biāo)記，當(dāng)B=0時(shí)表示第i件物品不取，當(dāng)B=1時(shí)表示第i件物品已取，初始化全部取0，以下算法是從后面的物品開始取起，通過B數(shù)組的取值把15種取法全部窮舉出來，價(jià)值MAX初始化為0。B[0]B[1]B[2]B[3]B[4]00000{初始化}00001{取第4件物品，容積為8，不超，價(jià)值為10，將MAX替換為10}00010｛取物品3，容積為5，不超，價(jià)值為7，不換｝00011｛取物品3、4，容積為13，超｝00100｛取物品2，容積為4，不超，價(jià)值為5，不換｝001010011000111……01110｛這是最佳方案｝0111110000｛當(dāng)B〔0〕＝1時(shí)停止，B〔0〕稱為哨兵｝生成B數(shù)組中數(shù)據(jù)的方法如下：fillchar(b,sizeof(b),0);whileb[0]=0dobeginj:=n;whileb[j]=1dodec(j);b[j]:=1;fori:=j+1tondob:=0;end；小結(jié)：以上每件物品只能取1件，所以取法只有0和1兩種情況，我們稱之為0、1背包，算法的時(shí)間復(fù)雜度為O（2N），在1秒內(nèi)N只能做到20。例1：選數(shù)（NOIP2002初中組復(fù)賽第2題）[問題描述]:已知n個(gè)整數(shù)x1,x2,…,xn，以及一個(gè)整數(shù)k（k＜n）。從n個(gè)整數(shù)中任選k個(gè)整數(shù)相加，可分別得到一系列的和。例如當(dāng)n=4，k＝3，4個(gè)整數(shù)分別為3，7，12，19時(shí)，

可得全部的組合與它們的和為：3＋7＋12=223＋7＋19＝297＋12＋19＝383＋12＋19＝34。現(xiàn)在，要求你計(jì)算出和為素?cái)?shù)共有多少種。例如上例，只有一種的和為素?cái)?shù)：3＋7＋19＝29。[輸入]：鍵盤輸入，格式為：n,k（1<=n<=20，k＜n）x1,x2，…,xn（1<=xi<=5000000）n[輸出]：屏幕輸出，格式為：一個(gè)整數(shù)（滿足條件的種數(shù)）。[輸入輸出樣例]:輸入：43371219輸出：1[算法分析]:本題應(yīng)用背包問題中取數(shù)的方法進(jìn)行窮舉，在取數(shù)的過程中，當(dāng)B數(shù)組中有K個(gè)1的時(shí)候?qū)?yīng)的K個(gè)數(shù)相加，再判斷是不是素?cái)?shù)。主要程序段如下：readln(n,k);sum:=0;fori:=1tondoread(a);fillchar(b,sizeof(b),0);whileb[0]=0dobeginj:=n;whileb[j]=1dodec(j);b[j]:=1;fori:=j+1tondob:=0;m:=0;fori:=1tondoifb=1thenm:=m+1;{統(tǒng)計(jì)1的個(gè)數(shù)}ifm=kthenbegin計(jì)算此種取數(shù)方法得到的和S；ifS是素?cái)?shù)thensum:=sum+1;end;end;例2：采藥(NOIP2005初中組復(fù)賽第3題)【問題描述】辰辰是個(gè)天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到是草藥的山洞里對他說：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大?！比绻闶浅匠?，你能完成這個(gè)任務(wù)嗎？一個(gè)到處都

【輸入文件】輸入文件medic.in的第一行有兩個(gè)整數(shù)T（1<=T<=1000）和M（1<=M<=100），用一T代表總共能夠用來采藥的時(shí)間，M代表山洞里的草藥的數(shù)目在1到100之間（包括1和100）的整數(shù)，和這株草藥的價(jià)值。個(gè)空格隔開，。接下來的M行每行包括兩個(gè)分別表示采摘某株草藥的時(shí)間【輸出文件】輸出文件medic.out包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值?！緲永斎搿?037110069112【樣例輸出】3【數(shù)據(jù)規(guī)模】對于30%的數(shù)M<=100?！舅惴ǚ治觥磕?0%的分?jǐn)?shù)，據(jù)，M<=10；對于全部的數(shù)據(jù)，本題如果采用上述方法來解，只能將M算到20，而這里M〈=100，所以只能比較好的算法是采用動(dòng)態(tài)規(guī)劃，為了能說清算法，現(xiàn)重新舉一個(gè)例子，若輸入：103344556表示背包的容量是10，有3種物品。用一個(gè)數(shù)組用來表示背包容量與其最大價(jià)值的關(guān)系，組count,用下標(biāo)表示容量，初始化為0。然后按物品的順序一一來統(tǒng)計(jì)此每種藥品對應(yīng)各種背包容量時(shí)得到的i件物品，背包容量為j時(shí)的最大價(jià)值Cmax(j)=MAX(Cmaxj,Pi+余下空間的最大價(jià)值Cmax(j-i物品所占的空間))，如上例中，根據(jù)物品的不斷增加，各容量背包得到的最大價(jià)上例中設(shè)置一個(gè)數(shù)時(shí)的最大價(jià)值，最大價(jià)值為：對于是第值不斷替換：容量12345678910價(jià)值序號(hào)0000000000100444444442004555999930045669101111[數(shù)據(jù)結(jié)構(gòu)]time,price數(shù)組分別用來存入時(shí)間和價(jià)值，count來存入背包的價(jià)值。vartime,price:array[1..100]oflongint;t:longint;i,m,j:integer;

count:array[0..1000]oflongint;beginassign(input,'medic.in');assign(output,'medic.out');reset(input);rewrite(output);readln(t,m);fori:=1tomdoreadln(time,price);fillchar(count,sizeof(count),0);fori:=1tomdoforj:=tdownto1dobeginif(j>=time)and(price+count[j-time]>count[j])thencount[j]:=price+count[j-time];end;{j>=time表示當(dāng)前的容量能放入背包，price+count[j-time]>count[j]表示第i件物品的價(jià)i件物品對于背包容量為j時(shí)余下空間的最大價(jià)值大于當(dāng)前背包容量為j時(shí)的最大值加上第價(jià)值}writeln(count[t]);close(input);close(output);end.例3：開心的金明（NOIP2006初中組復(fù)賽