回溯法CONTENTS子集和問題最小長度電路板排列問題子集和問題Description子集和問題的一個實例為〈S,t〉。其中，S={1x，2x，…，nx}是一個正整數的集合，c是一個正整數。子集和問題判定是否存在S的一個子集S1，使得S1中的所有元素之和等于c。試設計一個解子集和問題的回溯法。子集和問題Input第1行有2個正整數n和c，n表示S的大小，c是子集和的目標值。接下來的1行中，有n個正整數，表示集合S中的元素。SampleInput51022654子集和問題Output輸出子集和問題的解。當問題無解時，輸出“Nosolution!”。

SampleInput51022654子集和問題Output輸出子集和問題的解。當問題無解時，輸出“Nosolution!”。

SampleInput51022654子集和問題analysis很容易想到的是一種構造子集的方法，選擇集合中的元素到子集中來，如果此時子集所有元素的和剛好為目標值的話，則找到解決方案，如果集合里面元素的和小于目標值的話就繼續在未選擇的元素當中選擇新的元素到子集中來。知道所有情況都枚舉完以后任然沒有找到解決方案的話，就是“NOSolution！”。子集和問題analysis但是很顯然窮舉所有子集的復雜度是2^n對于這個復雜度，計算機是很難承受的。到規模超過30的時候，已經幾乎出不了結果了。所以采用一種更加快速的非遞歸回溯算法。子集和問題非遞歸回溯算法*思想從第一個元素開始，如果此時當前的元素不在集合內的話，將這個元素加到子集當中來，將sum加上這個元素的值。然后判斷如果sum恰好為目標值c的話，就返回正值并且打印結果。如果sum>c的話則舍棄當前這個元素，修改標記數組，并且將sum減去這個元素的值。只要還有元素沒有判斷就繼續選擇。直到第n個元素，如果第n個元素判斷完還沒有找到解的話，就回溯到上一次選擇的那個點，將其從集合里面刪除并從它后一個點繼續重復前面的操作。如果回溯的時候回溯到了第一個元素之前的話呢，表示這個時候要么所有元素都加入到集合都不夠，或者是所有的情況都找過了還是沒有解決方案，這個時候返回無解子集和問題analysis只要找到結果程序理解結束比遞歸要好很多，不必要遍歷整個解答樹。沒有認真分析過它的復雜的，但是至少在oj遞歸超時，這個不超時。最小長度電路板排列問題Description將n塊電路板以最佳排列方式插入帶有n個插槽的機箱中。n塊電路板的不同排列方式對應于不同的電路板插入方案。設B={1,2,…,n}是n塊電路板的集合，L={N1,N2,…,Nm}是連接這n塊電路板中若干電路板的m個連接塊。Ni是B的一個子集，且Ni中的電路板用同一條導線連接在一起。設x表示n塊電路板的一個排列，即在機箱的第i個插槽中插入的電路板編號是x[i]。x所確定的電路板排列Density(x)密度定義為跨越相鄰電路板插槽的最大連線數。設n=8,m=5，給定n塊電路板及其m個連接塊：B={1,2,3,4,5,6,7,8}，N1={4,5,6}，N2={2,3}，N3={1,3}，N4={3,6}，N5={7,8};其中兩個可能的排列如圖所示，則該電路板排列的密度分別是2，3。左圖中，跨越插槽2和3,4和5，以及插槽5和6的連線數均為2。插槽6和7之間無跨越連線。其余插槽之間只有1條跨越連線。在設計機箱時，插槽一側的布線間隙由電路板的排列的密度確定。因此，電路板排列問題要求對于給定的電路板連接條件(連接塊)，確定電路板的最佳排列，使其具有最小密度。最小長度電路板排列問題問題分析電路板排列問題是NP難問題，因此不大可能找到解此問題的多項式時間算法。考慮采用回溯法系統的搜索問題解空間的排列樹，找出電路板的最佳排列。設用數組B表示輸入。B[i][j]的值為1當且僅當電路板i在連接塊Nj中。設total[j]是連接塊Nj中的電路板數。對于電路板的部分排列x[1:i]，設now[j]是x[1:i]中所包含的Nj中的電路板數。由此可知，連接塊Nj的連線跨越插槽i和i+1當且僅當now[j]>0且now[j]！=total[j]。用這個條件來計算插槽i和i+1間的連線密度。最小長度電路板排列問題算法效率在解空間排列樹的每個節點處，算法Backtrack花費O(m)計算時間為每個兒子節點計算密度。因此計算密度所消耗的總計算時間為O(mn!)。另外，生成排列樹需要O(n!)時間。每次更新當前最