回溯法：子集和問題 最小長度電路板排列問題

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

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

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