解：往屆同學答案，可用貪心算法改善f初值;亦可以根據(jù)X.t[]用貪心算法估計在任務1,2,…，X.length分派后，該路徑總執(zhí)行時間的上界，與f比較來剪枝(程序中用X.Time與之比較，并未實現(xiàn)下述算法思想中的限界函數(shù)。當然，其貪心法求k機調(diào)度問題的上界比較復雜，可以用更簡單的貪心規(guī)則：按執(zhí)行時間降序排列，依次分配給機器1,2,..k,k,k-1…1,1,2…)。算法思想：將n個任務按照所需時間非遞減排序，得到任務序列1，2，3，4…….,n，滿足時間關系t[1]<t[2]<……<t[n].限界函數(shù)：將n個任務中的前k個任務分配給當前k個機器，然后將第k+1個任務分配給最早完成已分配任務的機器，依次進行，最后點所需的時間超過這個已知的最優(yōu)值，則刪掉以此節(jié)點為根的子樹。否則更新最優(yōu)值。找出這些機器最終分配任務所需時間最長的，此時間作為分支限界函數(shù)。優(yōu)先級：哪臺機器完成當前任務的時間越早，也就是所有機器中最終停機時間越早，優(yōu)先級就越高，即被選作最小堆中的堆頂，作為擴展節(jié)點。設task[n]用來記錄最優(yōu)的調(diào)度順序每個節(jié)點具有信息：{Parent：父親節(jié)點，Level：節(jié)點所在深度加1，Ctime：運行到當前節(jié)點所用時間}①當level<=k時（不能用界限函數(shù)來剪枝，也不需要判斷優(yōu)先級），由于機器還未裝滿（即前面的k個任務其實是同時加入的），可以令Ctime=0，②當level>k時（需要界限函數(shù)來剪枝，需要判斷優(yōu)先級），Ctime就是運行到當前狀態(tài)所用的總時間，Ctime作為優(yōu)先級函數(shù)，即從最小堆中選取Ctime最小的節(jié)點優(yōu)先。當找出第一個解節(jié)點時，記錄此時的Ctime作為目標函數(shù)值，以后生成的節(jié)點的Ctime大于該目標函數(shù)值時，就可以剪掉該節(jié)點，如此下去一直到最小堆為空為止。上述就是最佳調(diào)度問題的分支限界算法。解空間樹的節(jié)點包括以下信息:Node{intPath[n];//節(jié)點對應的解空間樹的路徑，即到該節(jié)點為止的策略記錄（分支限界一定要有記錄）intT[k];//在本策略下的每臺機器的運行時間（每）intTime;//本策略的總執(zhí)行時間，為每臺機器運行時間的最大值（max優(yōu)化的目標）intlength;//本節(jié)點的深度,即當前處理的作業(yè)（擴展）}算法實現(xiàn)：ProcBestDispatch(intn,intk,intt[]){NodeBoot,X,P,result;//Boot為根節(jié)點，result保存最優(yōu)解intf;//記錄當前最優(yōu)解的執(zhí)行時間f=n*max(t[]);//初始化Boot.T[n]={0};//每臺機器的運行時間Boot.Time=0;//機器運行時間的最大值Boot.Path[n]={0};//解空間樹的路徑，即到該節(jié)點為止的策略記錄Boot.length=0;//初始化根節(jié)點（本節(jié)點的深度,即當前處理的作業(yè)）//f賦初值AddHeap(Boot);//根節(jié)點加入堆中，堆中元素按照Time值由小到大排序While(!Heap.empty())do{P=DeleteMinHeap();//P為當前優(yōu)先級最高的點fori=1tokdo//擴展P的k個子節(jié)點X=Newnode(P.Path[],P.T[],P.length+1);X.Path[X.length]=i;X.T[i]=X.T[i]+t[X.length];X.Time=max(X.T[]);ifX.length==nthen//X為葉節(jié)點ifX.Time<fthen//X的執(zhí)行時間小于已知最優(yōu)解f=X.Time;//將X設為最優(yōu)解result=X;//當前最優(yōu)解的執(zhí)行時間end{if}else//X為中間節(jié)點ifX.Time<fthenAddHeap(X);end{if}//X的當前執(zhí)行時間小于已知最優(yōu)解則加入堆中，否則剪去end{if}end{for}end{while}end{BestDispatch}二、1.子集合問題：設n個不同的正數(shù)構(gòu)成的集合S，求使得和為某數(shù)M的S的所有子集。(回溯算法)解：設S={a1,a2,..,an}，求S滿足條件的所有子集A。用回溯算法，解向量為<x1,x2,…,xn>，xi=0,1，其中xi=1當且僅當ai∈A。部分向量<x1,x2,…,xk>表示已經(jīng)考慮了對a1,a2,…ak的選擇，結(jié)點分支的約束條件為B(i)=（且ak+1+,如果先將S按升序排列的話）。算法描述略。最壞復雜度O(2n)。a=0：選第一個元素①b=1時，從b=1直到b=n開始選，看看之后的和有沒有合適的（不選的情況，加起來大于了）②b=2時，從b=2開始選，（即選第0個，不選第一個）A=1：不選第一個，選第二個2.如圖所示，一個4階Latin方是一個4X4的方格，在它的每個方格內(nèi)填入1,2,3或4，并使得每個數(shù)字在每行、每列都恰好出現(xiàn)一次。用回溯法求出所有第一行為1,2,3,4的所有4階Latin方。將每個解的第2行到第4行的數(shù)字從左到右寫成一個序列。如圖中的解是<3,4,1,2,4,3,2,1