經(jīng)典算法設(shè)計(jì)方法大雜燴(編輯修改稿)
2025-06-12 20:43 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 找錢(qián)時(shí)，為使找回的零錢(qián)的硬幣數(shù)最少，不考慮找零錢(qián)的所有各種發(fā)表方案，而是從最大面值的幣種開(kāi)始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當(dāng)不足大面值幣種的金額時(shí)才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這里總是最優(yōu)，是因?yàn)殂y行對(duì)其發(fā)行的硬幣種類(lèi)和硬 幣面值的巧妙安排。如只有面值分別為 5 和 11 單位的硬幣，而希望找回總額為 15單位的硬幣。按貪婪算法，應(yīng)找 1 個(gè) 11單位面值的硬幣和 4個(gè) 1單位面值的硬幣，共找回 5個(gè)硬幣。但最優(yōu)的解應(yīng)是 3個(gè) 5 單位面值的硬幣。 【問(wèn)題】裝箱問(wèn)題 問(wèn)題描述：裝箱問(wèn)題可簡(jiǎn)述如下：設(shè)有編號(hào)為 0、 …、 n1 的 n 種物品，體積分別為 v0、 v…、 vn1。將這 n種物品裝到容量都為 V 的若干箱子里。約定這 n種物品的體積均不超過(guò) V，即對(duì)于 0≤ in，有 0vi≤ V。不同的裝箱方案所需要的箱子數(shù)目可能不同。裝箱問(wèn)題要求使裝盡這 n種物品的箱子數(shù) 要少。 若考察將 n種物品的集合分劃成 n個(gè)或小于 n 個(gè)物品的所有子集，最優(yōu)解就可以找到。但所有可能劃分的總數(shù)太大。對(duì)適當(dāng)大的 n，找出所有可能的劃分要花費(fèi)的時(shí)間是無(wú)法承受的。為此，對(duì)裝箱問(wèn)題采用非常簡(jiǎn)單的近似算法，即貪婪法。該算法依次將物品放到它第一個(gè)能放進(jìn)去的箱子中，該算法雖不能保證找到最優(yōu)解，但還是能找到非常好的解。不失一般性，設(shè) n件物品的體積是按從大到小排好序的，即有 v0≥ v1≥…≥ vn1。如不滿(mǎn)足上述要求，只要先對(duì)這 n件物品按它們的體積從大到小排序，然后按排序結(jié)果對(duì)物品重新編號(hào)即可。裝箱算法簡(jiǎn)單描述如下 ： {輸入箱子的容積； 輸入物品種數(shù) n； 按體積從大到小順序，輸入各物品的體積； 預(yù)置已用箱子鏈為空； 預(yù)置已用箱子計(jì)數(shù)器 box_count 為 0； for(i=0； i n； i++) {從已用的第一只箱子開(kāi)始順序?qū)ふ夷芊湃胛锲?i的箱子 j； if(已用箱子都不能再放物品 i) {另用一個(gè)箱子，并將物品 i放入該箱子； box_count++； else 將物品 i放入箱子 j； 上述算法能求出需要的箱子數(shù) box_count，并能求出各箱子所裝物品。下面的例子說(shuō)明該算法不一定能找到最優(yōu)解，設(shè)有 6 種物品，它們的體積分別為：60、 4 3 20和 20 單位體積，箱子的容積為 100 個(gè)單位體積。按上述算法計(jì)算，需三只箱子，各箱子所裝物品分別為：第一只箱子裝物品 3；第二只箱子裝物品 5；第三只箱子裝物品 6。而最優(yōu)解為兩只箱子，分別裝物品 5和 6。 若每只箱子所裝物品用鏈表來(lái)表示，鏈表首結(jié)點(diǎn)指針存于一個(gè)結(jié)構(gòu)中，結(jié)構(gòu)記錄尚剩余的空間量和該箱子所裝物品鏈表的首指針。另將 全部箱子的信息也構(gòu)成鏈表。以下是按以上算法編寫(xiě)的程序。 【程序】 include include typedef struct ele {int vno； struct ele*link； }ELE； typedef struct hnode {int remainder； ELE*head； Struct hnode*next； }HNODE； void main() {int n,i,box_count,box_volume,*a； HNODE*box_h,*box_t,*j； ELE*p,*q； Printf(輸入箱子容積 \n)； Scanf(%d,amp。box_volume)； Printf(輸入物品種數(shù) \n)； Scanf(%d,amp。n)； A=(int*)malloc(sizeof(int)*n)； Printf(請(qǐng)按體積從大到小順序輸入各物品的體積： )； For(i=0； i n； i++)scanf(%d,a+i)； Box_h=box_t=NULL； Box_count=0； For(i=0； i n； i++) {p=(ELE*)malloc(sizeof(ELE))； pvno=i； for(j=box_h； j！ =NULL； j=jnext) if(jremainder=a[i])break； if(j==NULL) {j=(HNODE*)malloc(sizeof(HNODE))； jremainder=box_volumea[i]； jhead=NULL； if(box_h==NULL)box_h=box_t=j； else box_t=boix_tnext=j； jnext=NULL； box_count++； else jremainder=a[i]； for(q=jnext； q！ =NULLamp。amp。qlink！ =NULL； q=qlink)； if(q==NULL) {plink=jhead； jhead=p； else {plink=NULL； qlink=p； printf(共使用了 %d 只箱子 ， box_count)； printf(各箱子裝物品情況如下： )； for(j=box_h,i=1； j！ =NULL； j=jnext,i++) {printf(第 %2d 只箱子， 還剩余容積 %4d，所裝物品有； \n,I,jremainder)； for(p=jhead； p！ =NULL； p=plink) printf(%4d,pvno+1)； printf(\n)； 任
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1