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

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

SampleInput51022654子集和問題Output輸出子集和問題的解。當(dāng)問題無解時(shí)，輸出“Nosolution!”。

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