貪心算法習(xí)題解析

背包問(wèn)題定義如下：輸入：正數(shù)輸出：，使得：最大；給出一個(gè)求解背包問(wèn)題的貪心算法，并證明其正確性。解：貪心思想：首先計(jì)算每種物品單位重量的價(jià)值，并進(jìn)行由大到小的排序，然后依據(jù)貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包，若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超出，則選擇單位重量?jī)r(jià)值次高的物品，以此類推，每次都是選擇當(dāng)前未放入背包的單位重量?jī)r(jià)值最高的物品，直到總重量大于或等于。優(yōu)化子結(jié)構(gòu)：設(shè)A是此背包問(wèn)題的優(yōu)化解，且A包含物品j，其中j的重量為w，則A’=A-{}是剩余的n-1個(gè)原重物品1,2,…,j-1,j+1,n以及重為的物品j中可裝入容量為M-w的背包問(wèn)題的優(yōu)化解。證明：利用反證法。假設(shè)A’不是該子問(wèn)題的優(yōu)化解，則存在B’是該子問(wèn)題的優(yōu)化解，由此可知B'的價(jià)值大于A'的價(jià)值，令B=B'+{}，則B的價(jià)值大于A的價(jià)值，這與A是此問(wèn)題的優(yōu)化解相矛盾。所以此問(wèn)題具有優(yōu)化子結(jié)構(gòu)。貪心選擇性：計(jì)算每種物品單位重量的價(jià)值，并進(jìn)行由大到小的排序。若，則存在背包問(wèn)題的一個(gè)最優(yōu)解使得。證明：設(shè)A是一個(gè)優(yōu)化解，設(shè)其第一個(gè)物品的選擇為(1)如果，則命題成立。(2)如果，則X1在全部放入背包總價(jià)值不會(huì)超過(guò)M的情況下，并沒(méi)有全部放入，設(shè)B滿足，(i=2,3,...,n)與A相同，且調(diào)整最終的價(jià)值不會(huì)超過(guò)M，則B是一個(gè)優(yōu)化解且滿足正確性證明：因?yàn)樗惴ㄌ幚磉^(guò)程按照最有子結(jié)構(gòu)和貪心選擇性依次處理背包問(wèn)題，則此算法具有正確性。2.寫出分支界限的一般算法。（利用爬山算法）解：1)構(gòu)造由根組成的單元素棧S，根節(jié)點(diǎn)的權(quán)值初始化為0；2)將可行解初始化為cost=；3)計(jì)算當(dāng)前棧頂?shù)臋?quán)值=父節(jié)點(diǎn)的權(quán)值+該擴(kuò)展分支的權(quán)值；4)IfTop(S)是目標(biāo)節(jié)點(diǎn)then根據(jù)該節(jié)點(diǎn)計(jì)算當(dāng)前可行解cost，cost=新的可行解；5)If當(dāng)前棧頂Top(S)的cost’>cost，則Pop(S)，且不再將其子節(jié)點(diǎn)入棧；6)將S的子節(jié)點(diǎn)按照其啟發(fā)式測(cè)度由大到小的順序壓入S；7)IfS空且cost=，then失敗;8)IfS空且cost!=，returncost;9)Elsegoto3.3.是一個(gè)可能解，當(dāng)且僅當(dāng)必是一個(gè)拓?fù)湫蛄?。證明：=>是一個(gè)可能解，而每個(gè)人的工作能力符合關(guān)系，則對(duì)于，若滿足偏序關(guān)系，則有；若不滿足偏序關(guān)系，則的分配無(wú)所謂順序，所以，必是一個(gè)拓?fù)湫蛄校?lt;=是一個(gè)拓?fù)湫蛄?，?duì)于，若滿足偏序關(guān)系，則有，其分配滿足；若不滿足偏序關(guān)系，則的分配無(wú)所謂順序，不妨使得分配情況滿足，于是將所有的工作分配完成之后，使得成立，則是一個(gè)分配任務(wù)的可能解。4.修改拓?fù)渑判蛩惴?，寫出?yán)格的分支界限算法。（使用爬山法）解：1)生成樹(shù)根root，其權(quán)值為解代價(jià)下界；2)將可行解的代價(jià)初始化為cost=；3)選擇偏序集中沒(méi)有前序元素的所有元素，根據(jù)加工后的代價(jià)矩陣元素，按權(quán)值由大到小依次入棧，作為root的子節(jié)點(diǎn)；4)Forroot的每個(gè)子節(jié)點(diǎn)v，其權(quán)值為加工后的代價(jià)矩陣元素加其父節(jié)點(diǎn)權(quán)值；5)如果此節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，且權(quán)值不大于cost，則令cost=當(dāng)前節(jié)點(diǎn)的權(quán)值，作為界限；6)如果此節(jié)點(diǎn)權(quán)值大于cost，則將此分支剪掉，其子節(jié)點(diǎn)不再入棧；7)S=S-{v};8)把v作為根，遞歸地處理S.5.給出求解旅行商問(wèn)題的詳細(xì)算法。解：1)根據(jù)各邊之間的權(quán)值，列出此問(wèn)題的初始代價(jià)矩陣；2)將代價(jià)矩陣進(jìn)行處理，每行（列）減去減去該行(列)的最小值，使得每行(列)至少有一個(gè)零，其余各元素非負(fù)，每行（列）所減去所有數(shù)的和即為解的代價(jià)下界；3)選擇滿足下列條件的邊(i,j)，使得，，所有包含(i,j)的解集合作為左子樹(shù)，所有不包含(i,j)的解集合作為右子樹(shù)；4)左子樹(shù)的代價(jià)下界不變，計(jì)算右子樹(shù)的代價(jià)：分別從變換后的代價(jià)矩陣的第i行第j列中找到具有最小代價(jià)的從i出發(fā)的邊(i,k)和進(jìn)入j邊(r,j)，將這兩條邊的代價(jià)與其父節(jié)點(diǎn)的解的代價(jià)下界求和，即為右子樹(shù)節(jié)點(diǎn)的代價(jià)下界；5)構(gòu)造左子樹(shù)根對(duì)應(yīng)的代價(jià)矩陣：矩陣中的第i行第j列應(yīng)該被刪除，并且代價(jià)矩陣的(j,i)元素的位置應(yīng)該被置為；6)計(jì)算左子樹(shù)的代價(jià)下界：此時(shí)左子樹(shù)的代價(jià)矩陣中可能出現(xiàn)某行或某列沒(méi)有0的情況，則需相應(yīng)的減去一個(gè)對(duì)應(yīng)行或列的最小數(shù)，于是可以獲得左子樹(shù)的新代價(jià)下界；7)構(gòu)造右子樹(shù)根對(duì)應(yīng)的代價(jià)矩陣：把代價(jià)矩陣的(j,i)元素的位置置為；8)計(jì)算右子樹(shù)的代價(jià)下界：此時(shí)右子樹(shù)的代價(jià)矩陣中可能出現(xiàn)某行或某列沒(méi)有