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