《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語言描述） 課件 第5章回溯法1

第5章走不下去就回退—回溯法5.1回溯法概述5.3基于子集樹框架的問題求解CONTENTS提綱5.4基于排列樹框架的問題求解5.2深度優(yōu)先搜索1/1265.1.1問題的解空間5.1回溯法概述求所有解類型：給定一個(gè)約束函數(shù)，需要求所有滿足約束條件的解。求最優(yōu)解類型：除了約束條件外還包含目標(biāo)函數(shù)，最后是求使目標(biāo)函數(shù)最大或者最小的最優(yōu)解。問題類型2/126一個(gè)復(fù)雜問題的解決方案往往是由若干個(gè)小的決策（即選擇）步驟組成的決策序列。問題的解可以表示成解向量x=（x0，x1，…，xn-1），其中分量xi對應(yīng)第i步的選擇，xi∈Si（0≤i≤n-1）。x中各個(gè)分量xi所有的取值的組合構(gòu)成問題的解向量空間，簡稱為解空間，解空間一般用樹形式來組織，也稱為解空間樹或者狀態(tài)空間樹。3/126解空間的一般結(jié)構(gòu)x0=v01A1結(jié)點(diǎn)B0結(jié)點(diǎn)A0x1=v1,0x0=v0,ax0=v0,0x0∈S0……………x1∈S1…葉子結(jié)點(diǎn)根結(jié)點(diǎn)x1=v1,bxn-1∈Sn-1高度為n+1包含問題的解4/12601234(a)一個(gè)連通圖x3=4x2=2x2=4x1=1012344(b)解空間x1=3i=1(根結(jié)點(diǎn))i=2i=3i=4(葉子結(jié)點(diǎn))例如，對于如圖5.1(a)所示的連通圖，現(xiàn)在要求從頂點(diǎn)0到頂點(diǎn)4的所有路徑（默認(rèn)為簡單路徑），這是一個(gè)求所有解問題。5/126

【例】農(nóng)夫（人）過河問題是這樣的，在河?xùn)|岸有一個(gè)農(nóng)夫、一只狼、一只雞和一袋谷子，只有當(dāng)農(nóng)夫在現(xiàn)場時(shí)，狼不會吃雞，雞也不會吃谷子，否則會出現(xiàn)狼吃雞或者雞吃谷子的沖突。另有一條小船，該船只能由農(nóng)夫操作，且最多只能載下農(nóng)夫和另一樣?xùn)|西。

設(shè)計(jì)一種將農(nóng)夫、狼、雞和谷子借助小船運(yùn)到河西岸的過河方案。6/126解③④⑤⑥⑦②①人、狼、雞、谷雞、谷

人、狼狼、谷人、雞狼、雞

人、谷人、狼、谷雞谷人、狼、雞狼人、雞、谷人、雞、谷狼人、狼、谷

雞雞人、狼、谷人、雞狼、谷人、狼、雞、谷人、狼、雞谷…………從東岸到西岸從西岸到東岸從東岸到西岸從西岸到東岸從東岸到西岸從東岸到西岸從西岸到東岸東岸西岸7/126回溯法是在解空間樹中按照深度優(yōu)先搜索方法從根結(jié)點(diǎn)出發(fā)搜索解。x0=a0xn-1=an-1葉子結(jié)點(diǎn)根結(jié)點(diǎn)高度為n+1x1=a15.1.2什么是回溯法8/126幾個(gè)概念活結(jié)點(diǎn)：指自身已生成但其孩子結(jié)點(diǎn)沒有全部生成的結(jié)點(diǎn)。擴(kuò)展結(jié)點(diǎn)：指正在產(chǎn)生孩子結(jié)點(diǎn)的結(jié)點(diǎn)。死結(jié)點(diǎn)：指其所有子結(jié)點(diǎn)均已產(chǎn)生的結(jié)點(diǎn)，此時(shí)應(yīng)往回移動（回溯）至最近的一個(gè)活結(jié)點(diǎn)處?；厮葸^程×s1si…si+1回溯再找其他路徑9/126回溯算法設(shè)計(jì)關(guān)鍵點(diǎn)根據(jù)問題的特性確定結(jié)點(diǎn)是如何擴(kuò)展的，不同的問題擴(kuò)展方式是不同的。例如，在有向圖中搜索從頂點(diǎn)s到頂點(diǎn)t的一條路徑，其擴(kuò)展十分簡單，就是從一個(gè)頂點(diǎn)找所有相鄰頂點(diǎn)。在解空間中按什么方式搜索解，實(shí)際上樹的遍歷主要有先根遍歷和層次遍歷，前者就是深度優(yōu)先搜索（DFS），后者就是廣度優(yōu)先搜索（BFS）?；厮莘ň褪遣捎蒙疃葍?yōu)先搜索解，下一章介紹的分支限界法則是采用廣度優(yōu)先搜索解。解空間通常十分龐大，如何高效地找到問題的解，通常采用一些剪支的方法實(shí)現(xiàn)?；厮莘?DFS+剪支10/126剪支：在解空間中搜索時(shí)提早終止某些分支的無效搜索，減少搜索的結(jié)點(diǎn)個(gè)數(shù)但不影響最終結(jié)果，從而提高了算法的時(shí)間性能。剪支策略可行性剪支：在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束條件的分支。例如，在雞兔同籠問題中，若a=3，b=8為例，兔數(shù)的取值范圍只能是0～2，因?yàn)?只或者更多只兔子時(shí)腿數(shù)就超過8了，不再滿足約束條件。最優(yōu)性剪支：用限界函數(shù)剪去得不到最優(yōu)解的分支。例如，在雞兔同籠問題中求雞最少的解，若已經(jīng)求出一個(gè)可行解的雞數(shù)為3，后面就不必搜索雞數(shù)大于3的結(jié)點(diǎn)。交換搜索順序：在搜索中改變搜索的順序，比如原先是遞減順序，可以改為遞增順序，或者原先是無序，可以改為有序，這樣可能減少搜索的總結(jié)點(diǎn)。11/126針對給定的問題確定其解空間，其中一定包含問題的解。確定結(jié)點(diǎn)的擴(kuò)展規(guī)則。采用深度優(yōu)先搜索方法搜索解空間，并在搜索過程中盡可能采用剪支函數(shù)避免無效搜索?；厮莘ㄇ蠼獾囊话悴襟E12/1265.1.4回溯法算法時(shí)間分析解空間樹共有n+1層（根結(jié)點(diǎn)為第0層，葉子結(jié)點(diǎn)為第n層）。第1層有m0個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有m1個(gè)子結(jié)點(diǎn)。第2層有m0m1個(gè)結(jié)點(diǎn)，同理，第3層有m0m1m2個(gè)結(jié)點(diǎn)，依此類推，第n層有m0m1…mn-1個(gè)結(jié)點(diǎn)。則采用回溯法求所有解的算法的執(zhí)行時(shí)間為

T(n)=m0+m0m1+m0m1m2+…+m0m1m2…mn-1。例如，在子集樹中有m0=m1=…=mn-1=c，對應(yīng)算法的時(shí)間復(fù)雜度為O(cn)，在排列樹中有m0=n，m1=n-1，…，mn-1=1，對應(yīng)算法的時(shí)間復(fù)雜度為O(n!)。13/1265.2深度優(yōu)先搜索深度優(yōu)先搜索是在訪問一個(gè)頂點(diǎn)v之后盡可能先對縱深方向進(jìn)行搜索。在解空間中搜索時(shí)類似樹的先根遍歷方式。14/1265.2.1圖的深度優(yōu)先遍歷圖遍歷是從圖中某個(gè)起始點(diǎn)出發(fā)訪問圖中所有頂點(diǎn)并且每個(gè)頂點(diǎn)僅訪問一次的過程，其頂點(diǎn)訪問序列稱為圖遍歷序列。采用深度優(yōu)先搜索方法遍歷圖稱為圖的深度優(yōu)先遍歷，得到遍歷序列稱為深度優(yōu)先遍歷序列，其過程是從起始點(diǎn)v出發(fā)，以縱向方式一步一步沿著邊訪問各個(gè)頂點(diǎn)。15/126從頂點(diǎn)v出發(fā)求深度優(yōu)先遍歷序列ans的算法如下：1 defDFS1(adj,v): #深度優(yōu)先遍歷3 ans.append(v) #訪問頂點(diǎn)v4 visited[v]=15 foruinadj[v]:#找到v的相鄰點(diǎn)u6 ifvisited[u]==0: #若頂點(diǎn)u尚未訪問7 DFS1(adj,u) #從u出發(fā)繼續(xù)搜索89 defDFS(adj,v):11 ans=[] #存放一個(gè)DFS序列12 visited=[0]*len(adj)#初始化所有元素為013 DFS1(adj,v)14 returnans16/1265.2.2深度優(yōu)先遍歷和回溯法的差別【例5-1】對于圖(a)的連通圖，求從頂點(diǎn)0到頂點(diǎn)4的所有路徑。0123417/126解01234采用深度優(yōu)先遍歷求u到v的所有路徑時(shí)是從頂點(diǎn)u出發(fā)以縱向方式進(jìn)行頂點(diǎn)搜索，用x存放一條路徑，用ans存放所有的路徑。如果當(dāng)前訪問的頂點(diǎn)u=v時(shí)，將找到的一條路徑x添加到ans中，同時(shí)從頂點(diǎn)u回退以便找其他路徑，否則找到u的所有相鄰點(diǎn)w，若頂點(diǎn)w尚未訪問則從w出發(fā)繼續(xù)搜索路徑。當(dāng)u出發(fā)的所有路徑搜索完畢，再從u回退。18/1261 importcopy2 defdfs11(adj,u,v,x): #深度優(yōu)先搜索4 x.append(u) #訪問頂點(diǎn)u5 visited[u]=16 ifu==v: #找到一條路徑7 ans.append(copy.deepcopy(x)) #將路徑x的拷貝添加到ans中8 visited[u]=0 #置u可以重新訪問9 x.pop() #路徑回退10 return11 forwinadj[u]: #找到u的相鄰點(diǎn)w12 ifvisited[w]==0: #若頂點(diǎn)w尚未訪問13 dfs11(adj,w,v,x) #從w出發(fā)繼續(xù)搜索14 visited[u]=0 #u出發(fā)的所有路徑找完后回退15 x.pop() #路徑回退基于深度優(yōu)先遍歷求解算法19/12617 defdfs1(adj,u,v): #求u到v的所有路徑18 globalvisited,ans19 ans=[]20 visited=[0]*len(adj) #初始化所有元素為021 x=[]22 dfs11(adj,u,v,x)23 returnans20/1261 defdfs21(adj,u,v,x): #回溯法3 ifu==v: #找到一條路徑4 ans.append(copy.deepcopy(x)) #將路徑x的拷貝添加到ans中5 else:6 forwinadj[u]: #找到u的相鄰點(diǎn)w7 ifvisited[w]==0: #若頂點(diǎn)w尚未訪問8 x.append(w)

#訪問v,將v添加到ans中9 visited[w]=110 dfs21(adj,w,v,x) #從w出發(fā)繼續(xù)搜索11 visited[w]=0 #從w回退到u12 x.pop()基于回溯法求解算法21/12614 defdfs2(adj,u,v): #求u到v的所有路徑15 globalvisited,ans16 ans=[] #存放所有路徑17 visited=[0]*len(adj) #初始化所有元素為018 x=[]19 x.append(u)

#起始點(diǎn)u添加中x中20 visited[u]=121 dfs21(adj,u,v,x)22 returnans22/126深度優(yōu)先遍歷主要考慮頂點(diǎn)u的前進(jìn)和回退，不需要專門表示回退到哪個(gè)頂點(diǎn)?；厮莘ㄖ饕紤]頂點(diǎn)u擴(kuò)展的子結(jié)點(diǎn)以及從子結(jié)點(diǎn)的回退，需要專門處理出發(fā)點(diǎn)u和子結(jié)點(diǎn)w之間的擴(kuò)展和回退關(guān)系。盡管都是采用深度優(yōu)先搜索，但后者解決問題的思路更清晰，特別是對于復(fù)雜的問題求解要方便得多。x3=4x2=2x2=4x1=1012344x1=3i=1(根結(jié)點(diǎn))i=2i=3i=4(葉子結(jié)點(diǎn))23/1265.2.3實(shí)戰(zhàn)—二叉樹的所有路徑（LeetCode257★）問題描述：給定一棵含n（1≤n≤100）個(gè)結(jié)點(diǎn)的二叉樹的根結(jié)點(diǎn)

root，結(jié)點(diǎn)值在[-100，100]內(nèi)，設(shè)計(jì)一個(gè)算法按任意順序返回所有從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑。

例如，對于如下圖的二叉樹，返回結(jié)果是{"1->2->5"，"1->3"}。

要求設(shè)計(jì)如下方法：

def

binaryTreePaths(self,

root)

->

List[str]:123524/126從根結(jié)點(diǎn)root出發(fā)搜索到每個(gè)葉子結(jié)點(diǎn)時(shí)構(gòu)成一條路徑x，將其轉(zhuǎn)換為路徑字符串tmp后添加的ans中。由于是樹結(jié)構(gòu)，不會重復(fù)訪問頂點(diǎn)，不必設(shè)置訪問標(biāo)記數(shù)組。問題求解—深度優(yōu)先遍歷25/1261 class

Solution:2

def

binaryTreePaths(self,

root)

->

List[str]:3

if

root==None:return

[]4

self.ans=[]5

x=[]

#存放一條路徑6

self.dfs(root,x) #dfs求ans7

return

self.ans26/1269

def

dfs(self,root,x):

#深度優(yōu)先遍歷10

x.append(root.val)11

if

root.left==None

and

root.right==None:

#找到一路徑12

tmp=str(x[0])

#路徑轉(zhuǎn)換為字符串13

for

i

in

range(1,len(x)):14

tmp+="->"+str(x[i])15

self.ans.append(tmp)16

else:17

if

root.left!=None:18

self.dfs(root.left,x)19

if

root.right!=None:20

self.dfs(root.right,x)21

x.pop()

#從結(jié)點(diǎn)root回退123527/126將給定的一棵樹看成是解空間，存放一條路徑的x就是一個(gè)解向量。從根結(jié)點(diǎn)root出發(fā)搜索，當(dāng)?shù)竭_(dá)一個(gè)葉子結(jié)點(diǎn)時(shí)構(gòu)成一條路徑，將解向量x轉(zhuǎn)換為路徑字符串tmp后添加的ans中，否則，從root擴(kuò)展出左右孩子結(jié)點(diǎn)，并從孩子結(jié)點(diǎn)回退的root。問題求解—回溯法28/1261 class

Solution:2

def

binaryTreePaths(self,root)

->

List[str]:3

if

root==None:return

[]4

self.ans=[]5

x=[]

#存放一條路徑6

x.append(root.val)7

self.dfs(root,x)

#dfs求ans8

return

self.ans29/12610

def

dfs(self,root,x):

#回溯算法11

if

root.left==None

and

root.right==None:

#找到一路徑12

tmp=str(x[0])

#路徑轉(zhuǎn)換為字符串13

for

i

in

range(1,len(x)):14

tmp+="->"+str(x[i])15

self.ans.append(tmp)16

else:17

if

root.left!=None:18

x.append(root.left.val)19

self.dfs(root.left,x)20

x.pop() #回溯21

if

root.right!=None:22

x.append(root.right.val)23

self.dfs(root.right,x)24

x.pop()

#回溯123530/1265.3.1子集樹算法框架概述解空間類型子集樹：所給的問題是從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集。例如在整數(shù)數(shù)組a中求和為目標(biāo)值target的所有解，每個(gè)元素a[i]只有選擇和不選擇兩種方式。排列樹：所給的問題是確定n個(gè)元素滿足某種性質(zhì)的排列。例如求全排列問題的解空間就是典型的排列樹。5.3基于子集樹框架的問題求解31/126子集樹算法框架x=[0]*MAXN #x存放解向量，這里作為全局變量defdfs(i): #求解子集樹的遞歸框架 ifi>n: #搜索到葉子結(jié)點(diǎn),輸出一個(gè)可行解

輸出一個(gè)解 else: forjinrange(下界,上界+1): #用j表示x[i]的所有可能候選值

x[i]=j

#產(chǎn)生一個(gè)可能的解分量

…

#其他操作 ifconstraint(i,j)andbound(i,j):

dfs(i+1) #滿足約束條件和限界函數(shù),繼續(xù)下一層

回溯x[i]

…

32/126問題描述：給定一個(gè)整數(shù)數(shù)組

nums，長度范圍是1～10，其中所有元素互不相同。求該數(shù)組所有可能的子集（冪集），結(jié)果中不能包含重復(fù)的子集，可以按任意順序返回冪集。

例如，nums=[1，2，3]，結(jié)果為[[]，[1]，[2]，[1，2]，[3]，[1，3]，[2，3]，[1，2，3]]。

要求設(shè)計(jì)如下成員方法：

def

subsets(self,

nums)

->

List[List[int]]5.3.2實(shí)戰(zhàn)—子集（LeetCode78★★）33/126解法1解向量為x，x[i]=1表示選取a[i]，x[i]=0表示不選取a[i]。01010101010101第0層第1層第2層第3層（葉子結(jié)點(diǎn)層）{1,2,3}{1,2}{1,3}{1}{2,3}{2}{3}{}34/1261 class

Solution:2

def

subsets(self,

nums)

->

List[List[int]]:3

self.ans,self.x=[],[]4

self.dfs(nums,0)5

return

self.ans35/1267

def

dfs(self,nums,i):

#回溯算法8

if

i==len(nums):

#到達(dá)一個(gè)葉子結(jié)點(diǎn)9

self.ans.append(copy.deepcopy(self.x))10

else:11

self.x.append(nums[i])

#選擇nums[i],

x中添加nums[i]12

self.dfs(nums,i+1)13

self.x.pop()

#回溯即刪除前面添加的nums[i]14

self.dfs(nums,i+1)

#不選擇nums[i],x中不添加nums[i]01010101010101第0層第1層第2層第3層（葉子結(jié)點(diǎn)層）{1,2,3}{1,2}{1,3}{1}{2,3}{2}{3}{}36/126解法2將x改為直接存放a的一個(gè)子集。設(shè)解向量x={x0，…，xi，…，xm-1}（m為x的長度，0≤m≤n）。x2=a[2]=3x1=3x1=a[1]=2x1=a[2]=3x0=a[0]=1x0=a[1]=2x0=a[2]=30,0,{}1,1,{1}2,2,{1,2}3,3,{1,2,3}2,3,{1,3}1,2,{2}1,3,{3}2,3,{2,3}i=0i=1i=2i=337/126每個(gè)結(jié)點(diǎn)的狀態(tài)為“i，j，x”，其中i為結(jié)點(diǎn)的層次，xi的取值范圍為a[j..n-1]，x為解向量。解空間中每個(gè)結(jié)點(diǎn)的x都是一個(gè)子集。0,0,{}x2=a[2]=3x1=3x1=a[1]=2x1=a[2]=3x0=a[0]=1x0=a[1]=2x0=a[2]=31,1,{1}2,2,{1,2}3,3,{1,2,3}2,3,{1,3}1,2,{2}1,3,{3}2,3,{2,3}i=0i=1i=2i=3ij38/1261 class

Solution:2

def

subsets(self,

nums)

->

List[List[int]]:3

self.ans,x=[],[]4

self.dfs(nums,x,0)5

return

self.ans39/1267

def

dfs(self,nums,x,i): #回溯算法8

self.ans.append(copy.deepcopy(x)) #找到一個(gè)解9

for

j

in

range(i,len(nums)):10

x.append(nums[j])11

self.dfs(nums,x,j+1)12

x.pop() #回溯即刪除前面添加的nums[j]40/126兩種解法的比較！41/126問題描述：給定n個(gè)整數(shù)數(shù)組nums，其中可能包含重復(fù)元素，請你返回該數(shù)組所有可能的子集（冪集）。解集不能包含重復(fù)的子集，返回的解集中子集可以按任意順序排列。

例如，nums={1，2，2}，結(jié)果為{{}，{1}，{1，2}，{1，2，2}，{2}，{2，2}}。

要求設(shè)計(jì)如下方法：

def

subsetsWithDup(self,

nums)

->

List[List[int]]:5.3.3實(shí)戰(zhàn)—子集Ⅱ（LeetCode90★★）42/126解法1由于這里nums中包含重復(fù)元素。如果直接采用5.3.2節(jié)的算法1會得到重復(fù)的子集。例如，nums[]={1，2，1}時(shí)，求解結(jié)果為{{1，2，1}，{1，2}，{1，1}，{1}，{2，1}，{2}，{1}，{}}，其中{1，2}和{2，1}重復(fù)，同時(shí){1}出現(xiàn)兩次。兩個(gè)相同的{1}容易消除，但{1，2}和{2，1}如何消除呢？可以采用先將nums排序的方法，如nums[]={1，1，2}，其結(jié)果為{{1，1，2}，{1，1}，{1，2}，{1}，{1，2}，{1}，{2}，{}}，這樣重復(fù)的子集的順序均相同，剩下的問題是消除順序相同的重復(fù)子集。43/126采用5.3.2節(jié)求a的冪集的算法1的思路，利用集合set實(shí)現(xiàn)去重（其元素為由x轉(zhuǎn)換的元組）。1 class

Solution:2

def

subsetsWithDup(self,

nums)

->

List[List[int]]:3

nums.sort()

#nums遞增排序4

self.ans,self.x=set(),[]5

self.dfs(nums,0)6

return

list(self.ans)44/1268

def

dfs(self,nums,i):

#回溯算法9

if

i==len(nums):

#到達(dá)一個(gè)葉子結(jié)點(diǎn)10

self.ans.add(tuple(self.x))11

else:12

self.x.append(nums[i])

#選擇nums[i],

x中添加nums[i]13

self.dfs(nums,i+1)14

self.x.pop()

#回溯15

self.dfs(nums,i+1) #不選擇nums[i],x不加nums[i]上述程序提交時(shí)通過，執(zhí)行用時(shí)為44ms，內(nèi)存消耗為16.3MB。45/126解法2采用5.3.2節(jié)求a的冪集的算法2的思路更方便！46/126每個(gè)結(jié)點(diǎn)的狀態(tài)為“i，j，x”，其中i為結(jié)點(diǎn)的層次，xi的取值范圍為a[j..n-1]，x為解向量。解空間中每個(gè)結(jié)點(diǎn)的x都是一個(gè)子集。0,0,{}x2=a[2]=3x1=3x1=a[1]=2x1=a[2]=3x0=a[0]=1x0=a[1]=2x0=a[2]=31,1,{1}2,2,{1,2}3,3,{1,2,3}2,3,{1,3}1,2,{2}1,3,{3}2,3,{2,3}i=0i=1i=2i=3ij47/1261 class

Solution:2

def

subsetsWithDup(self,

nums)

->

List[List[int]]:3

nums.sort() #nums遞增排序4

self.ans,x=[],[]5

self.dfs(nums,x,0)6

return

self.ans48/1268

def

dfs(self,nums,x,i): #回溯算法9

self.ans.append(copy.deepcopy(x))10

for

j

in

range(i,len(nums)):11

if

j>i

and

nums[j]==nums[j-1]:continue13

x.append(nums[j])14

self.dfs(nums,x,j+1)15

x.pop()0,0,{}x0=a[0]=1x0=a[1]=1x0=a[2]=21,1,{1}1,2,{1}1,3,{3}i=0i=1ij………49/126上述程序提交時(shí)通過，執(zhí)行用時(shí)為36ms，內(nèi)存消耗為15.2MB。50/126解法2的時(shí)空性能更好，為什么？問題描述：給定n個(gè)整數(shù)的數(shù)組nums和一個(gè)整數(shù)target。向數(shù)組中的每個(gè)整數(shù)前添加'+'或'-'

，然后串聯(lián)起所有整數(shù)，可以構(gòu)造一個(gè)表達(dá)式，例如，nums={2，1}，可以在2之前添加'+'，在1之前添加'-'，然后串聯(lián)起來得到表達(dá)式

“+2-1”。

設(shè)計(jì)一個(gè)算法求可以通過上述方法構(gòu)造的運(yùn)算結(jié)果等于target的不同表達(dá)式的數(shù)目。

要求設(shè)計(jì)如下方法：

def

findTargetSumWays(self,

nums,

target)

->

int:5.3.4實(shí)戰(zhàn)—目標(biāo)和（LeetCode494★★）51/126解用ans表示滿足要求的解個(gè)數(shù)（初始為0），設(shè)置解向量x=（x0，x1，…，xn-1），xi表示nums[i]（0≤i≤n-1）前面添加的符號，xi只能在'+'和'-'符號在二選一，所以該問題的解空間為子集樹。用expv表示當(dāng)前運(yùn)算結(jié)果（初始為0）。對于解空間中第i層的結(jié)點(diǎn)A，若xi選擇'+'，則expv+=nums[i]；若xi選擇'-'，則expv-=nums[i]，在回退到A時(shí)要恢復(fù)expv。x[0]nums[0]x[1]nums[1]…

x[n-1]nums[n-1]52/126找到一個(gè)解，置ans+=1。由于該問題只需要求最后的解個(gè)數(shù)，所以不必真正設(shè)計(jì)解向量x，僅僅設(shè)計(jì)expv即可。53/1261 class

Solution:2

def

findTargetSumWays(self,

nums,

target)

->

int:3

self.ans=04

self.dfs(nums,target,0,0)5

return

self.ansdfs(nums,target,i,expv)54/1267

def

dfs(self,nums,target,i,expv):

#回溯算法8

if

i==len(nums):

#到達(dá)一個(gè)葉子結(jié)點(diǎn)9

if

expv==target:self.ans+=1

#找到一個(gè)解10

else:11

expv+=nums[i]

#nums[i]前選擇'+'12

self.dfs(nums,target,i+1,expv)13

expv-=nums[i]

#回溯：恢復(fù)expv14

expv-=nums[i]

#nums[i]前選擇'-'15

self.dfs(nums,target,i+1,expv)16

expv+=nums[i]

#回溯：恢復(fù)expv55/126說明：上述程序提交時(shí)出現(xiàn)超時(shí)現(xiàn)象，但同樣的思路采用C/C++或者Java編程時(shí)提交通過。56/126給定n個(gè)不同的正整數(shù)集合a=（a0，a1，…，an-1）和一個(gè)正整數(shù)t，要求找出a的子集s，使該子集中所有元素的和為t。例如，當(dāng)n=4時(shí)，a=（3，1，5，2），t=8，則滿足要求的子集s為（3，5）和（1，5，2）。5.3.5子集和問題57/126解與求冪集問題一樣，該問題的解空間是一棵子集樹（因?yàn)槊總€(gè)整數(shù)要么選擇要么不選擇）。求滿足約束函數(shù)的所有解。58/1261）無剪支a=（3，1，5，2），t=8010100101010101010101010101011086631117552000011996444108853333結(jié)點(diǎn)層次i=0i=1i=2i=3i=4sum=3159/1261 cnt=0 #累計(jì)解個(gè)數(shù)2 sum=0 #累計(jì)搜索的結(jié)點(diǎn)個(gè)數(shù)3 defdisp(a): #輸出一個(gè)解4 globalcnt,x5 cnt+=1;print("第%d個(gè)解,"%(cnt),end='')6 print("選取的數(shù)為:",end='')7 foriinrange(0,len(x)):8 ifx[i]==1:print(a[i],end='')9 print()60/12611 defdfs1(a,t,cs,i): #回溯算法12 globalsum,x13 sum+=114 ifi>=len(a):

#到達(dá)一個(gè)葉子結(jié)點(diǎn)15 ifcs==t:disp(a) #找到一個(gè)滿足條件的解,輸出16 else: #沒有到達(dá)葉子結(jié)點(diǎn)17 x[i]=1 #選取整數(shù)a[i]18 dfs1(a,t,cs+a[i],i+1)19 x[i]=0 #不選取整數(shù)a[i]20 dfs1(a,t,cs,i+1)61/12622 defsubs1(a,t): #求解子集和問題23 globalx24 x=[0]*len(a) #解向量25 print("求解結(jié)果")26 dfs1(a,t,0,0) #i從0開始27 print("sum=",sum)62/1262）左剪支當(dāng)搜索到第i（0≤i<n）層結(jié)點(diǎn)時(shí)，cs表示當(dāng)前已經(jīng)選取的整數(shù)和（其中不包含a[i]），判斷選擇a[i]是否合適：若cs+a[i]>t，不必繼續(xù)該路徑，終止搜索，也就是左剪支。若cs+a[i]≤t，沿著該路徑繼續(xù)下去可能會找到解，不能終止。簡單地說，僅僅擴(kuò)展?jié)M足cs+a[i]≤t的左孩子結(jié)點(diǎn)。a=（3，1，5，2），t=80101001010101010101010101011086631117552000096444108853333結(jié)點(diǎn)層次i=0i=1i=2i=3i=4cs=4sum=2763/1261 defdfs2(a,t,cs,i): #回溯算法2 globalsum,x3 sum+=14 ifi>=len(a):

#到達(dá)一個(gè)葉子結(jié)點(diǎn)5 ifcs==t:disp(a) #找到一個(gè)滿足條件的解,輸出6 else: #沒有到達(dá)葉子結(jié)點(diǎn)7 ifcs+a[i]<=t: #左孩子結(jié)點(diǎn)剪支8 x[i]=1 #選取整數(shù)a[i]9 dfs2(a,t,cs+a[i],i+1)10x[i]=0 #不選取整數(shù)a[i]11dfs2(a,t,cs,i+1)64/1263）右剪支考慮是否擴(kuò)展右孩子結(jié)點(diǎn)。當(dāng)搜索到第i（0≤i<n）層的某個(gè)結(jié)點(diǎn)時(shí)，用rs表示余下的整數(shù)和，即rs=a[i]+…+a[n-1]（包含a[i]）。如果不選擇a[i]，此時(shí)剩余的所有整數(shù)和為rs=rs-a[i]，若cs+rs<t成立，說明即便選擇所有剩余整數(shù)其和都不可能達(dá)到t。右剪支就是僅僅擴(kuò)展?jié)M足cs+rs≥t的右孩子結(jié)點(diǎn)。a=（3，1，5，2），t=801010010101010110,118,06,06,21,21,70,70,89,24,24,710,08,08,23,23,73,8rs=8,rs=rs-1=70+rs=7<tsum=1065/1261 defdfs3(a,t,cs,rs,i): #回溯算法2 globalsum,x3 sum+=14 ifi>=len(a): #到達(dá)一個(gè)葉子結(jié)點(diǎn)5 ifcs==t:disp(a) #找到一個(gè)解,輸出6 else: #沒有到達(dá)葉子結(jié)點(diǎn)7 rs-=a[i] #求剩余的整數(shù)和8 ifcs+a[i]<=t: #左孩子結(jié)點(diǎn)剪支9 x[i]=1 #選取整數(shù)a[i]10 dfs3(a,t,cs+a[i],rs,i+1)11 ifcs+rs>=t: #右孩子結(jié)點(diǎn)剪支12 x[i]=0 #不選取整數(shù)a[i]13 dfs3(a,t,cs,rs,i+1)14 rs+=a[i] #恢復(fù)剩余整數(shù)和(回溯)66/12616 defsubs3(a,t): #求解子集和問題17 globalx18 x=[0]*len(a) #解向量19 rs=020 foreina:rs+=e #或者rs=sum(a)21 print("求解結(jié)果")22 dfs3(a,t,0,rs,0) #i從0開始23 print("sum=",sum)67/126盡管通過剪支提高了算法的性能，但究竟剪去了多少結(jié)點(diǎn)與具體的實(shí)例數(shù)據(jù)相關(guān)。上述算法最壞情況下算法的時(shí)間復(fù)雜度仍然為O(n×2n)。算法分析68/126有n個(gè)集裝箱要裝上一艘載重量為t的輪船，其中集裝箱i（0≤i≤n-1）的重量為wi。不考慮集裝箱的體積限制，現(xiàn)要選出重量和小于等于t并且盡可能重的若干集裝箱裝上輪船。例如，n=5，t=10，w={5，2，6，4，3}時(shí)，其最佳裝載方案有兩種即（1，1，0，0，1）和（0，0，1，1，0），對應(yīng)集裝箱重量和達(dá)到最大值t。5.3.6簡單裝載問題69/126解與子集和問題類似。當(dāng)搜索到第i（0≤i<n）層的結(jié)點(diǎn)時(shí)，cw表示當(dāng)前選擇的集裝箱重量和，rw表示余下集裝箱的重量和，即 rw=w[i]+…+w[n-1]（含w[i]）此時(shí)處理集裝箱i，先從rw中減去w[i]即置rw-=w[i]。cw,rw第i層cw1,rw第i+1層rw=rw-w[i]70/126采用的剪支操作如下：左剪支：檢查當(dāng)前集裝箱被選中后總重量是否超過t，若是則剪支，即僅僅擴(kuò)展?jié)M足cw+w[i]≤t的左孩子結(jié)點(diǎn)。右剪支：如果不選擇集裝箱i，此時(shí)剩余的所有整數(shù)和為rw，若cw+rw≤bestw成立（bestw是當(dāng)前找到的最優(yōu)解的重量和），說明即便選擇所有剩余集裝箱其重量和都不可能達(dá)到bestw，所有僅僅擴(kuò)展?jié)M足cw+rw>bestw的右孩子結(jié)點(diǎn)。cw,rw第i層cw1,rw1第i+1層cw+w[i]≤t1cw,rw10cw+rw>bestw71/1262 defdfs(w,t,cw,rw,i): #回溯算法5 ifi>=len(w):

#到達(dá)一個(gè)葉子結(jié)點(diǎn)6 ifcw>bestw: #找到更優(yōu)解7 bestw=cw #保存更優(yōu)解8 bestx=copy.deepcopy(x) #深拷貝9 else: #尚未找完所有集裝箱10 rw-=w[i]

#求剩余集裝箱的重量和11 ifcw+w[i]<=t:

#左剪支12 x[i]=1 #選取集裝箱i13 cw+=w[i] #累計(jì)所選集裝箱的重量和14 dfs(w,t,cw,rw,i+1)15 cw-=w[i] #回溯cw16 ifcw+rw>bestw:

#右剪支17 x[i]=0 #不選擇集裝箱i18 dfs(w,t,cw,rw,i+1)19 rw+=w[i]

#回溯rw72/12621 defloading(w,t): #求解簡單裝載問題22 globalx,bestx,bestw,sum23 x=[0]*len(w) #解向量24 bestx=[0]*len(w) #存放最優(yōu)解向量25 bestw=0 #存放最優(yōu)解的總重量26 sum=0 #累計(jì)搜索的結(jié)點(diǎn)個(gè)數(shù)27 rw=028 foreinw:rw+=e29 dfs(w,t,0,rw,0)30 print("求解結(jié)果")31 foriinrange(0,len(w)): #輸出最優(yōu)解32 ifbestx[i]==1:print("選取第%d個(gè)集裝箱"%(i))33 print("總重量=",bestw)34 print("sum=",sum)73/126解空間樹中有2n+1-1個(gè)結(jié)點(diǎn)，葉子結(jié)點(diǎn)為2n個(gè)。每找到一個(gè)更優(yōu)解時(shí)需要將x復(fù)制到bestx（執(zhí)行時(shí)間為O(n)）。所以最壞情況下算法的時(shí)間復(fù)雜度為O(n×2n)。算法分析74/126有n個(gè)編號為0～n-1的物品，重量為w={w0，w1，…，wn-1}，價(jià)值為v={v0，v1，…，vn-1}，給定一個(gè)容量為W的背包。從這些物品中選取全部或者部分物品裝入該背包中，每個(gè)物品要么選中要么不選中，即物品不能被分割，找到選中物品不僅能夠放到背包中而且價(jià)值最大的方案（最大價(jià)值）。W=6結(jié)果為8物品編號重量w價(jià)值v0541342233115.2.30/1背包問題75/126解1）存儲結(jié)構(gòu)設(shè)計(jì)1 classGoods: #物品類2 def__init__(self,x,y,z):3 self.no=x #物品的編號4 self.w=y #物品的重量5 self.v=z #物品的價(jià)值6 def__lt__(self,other): #用于按v/w遞減排序7 return1.0*self.v/self.w>=1.0*other.v/other.w物品編號重量w價(jià)值v054134223311g=[Goods(0,5,4),Goods(1,3,4),Goods(2,2,3),Goods(3,1,1)]76/126解向量x=（x0，x1，…，xn-1），xi=1表示選擇物品i，xi=0表示不選擇物品i。最優(yōu)解向量用bestx表示，最大價(jià)值用bestv表示（初始為0）。77/1262）左剪支左剪支與子集和問題的類似。當(dāng)搜索到第i（0≤i<n）層的某個(gè)結(jié)點(diǎn)時(shí)，cw表示當(dāng)前選擇的物品重量和（其中不包含w[i]）。檢查當(dāng)前物品被選中后總重量是否超過W，若超過則剪支，即僅僅擴(kuò)展?jié)M足cw+w[i]≤W的左孩子結(jié)點(diǎn)。選擇物品i第i層78/1263）右剪支采用限界函數(shù)（上界函數(shù)）。將所有物品g按單位重量價(jià)值遞減排序。例如前面表排序后的結(jié)果如下，序號i發(fā)生了改變，后面改為按i而不是物品編號no的順序搜索。序號i物品編號no重量w價(jià)值vv/w02231.511341.32311130540.879/126第i層結(jié)點(diǎn)出發(fā)的最大可能價(jià)值：cw表示當(dāng)前選擇的物品重量和（不含w[i]），cv表示當(dāng)前選擇的物品價(jià)值和（不含v[i]）。此時(shí)背包剩余容量為rw=W-cw，如果按背包容量連續(xù)選擇物品i及其后面的物品，直到裝滿，其價(jià)值一定是最大的（因?yàn)槲锲钒磛/w遞減排序），最大價(jià)值為r(i)：第i層第i+1層第k-1層第k層cv，cw試探：物品i～k-1可以整個(gè)裝入，物品k只能部分裝入80/126第i層結(jié)點(diǎn)：如果不選擇物品i時(shí)，此時(shí)背包剩余容量為rw=W-cw。余下重量的物品的最大價(jià)值r(i+1)：x[i]=0第i層第i+1層…第k-1層第k層cvr(i+1)81/1261 defbound(cw,cv,i): #計(jì)算第i層結(jié)點(diǎn)的上界函數(shù)值2 globalg,W,n3 rw=W-cw #背包的剩余容量4 b=cv #表示物品價(jià)值的上界值5 j=i6 whilej<nandg[j].w<=rw:7 rw-=g[j].w #選擇物品j8 b+=g[j].v #累計(jì)價(jià)值9 j+=110 ifj<n: #最后物品k=j+1只能部分裝入11 b+=1.0*g[j].v/g[j].w*rw12 returnb限界函數(shù)不選擇物品i時(shí)這條路徑走下去能夠選擇物品的最大價(jià)值為bound(cw,cv,i+1)。對于第i層結(jié)點(diǎn)實(shí)參為i+1剪支：僅僅擴(kuò)展bound(cw,cv,i+1)>bestv的右孩子結(jié)點(diǎn)。82/126序號i物品編號no重量w價(jià)值vv/w02231.511341.32311130540.8右剪支實(shí)例0,06,85,72,36,8,65,7,7.811,122,3,6.40,0,6.6(cw,cv)(cw,cv,ub)bestv=8bound(cw,cv,i+1)≤bestv83/1261 defdfs(cw,cv,i): #回溯算法2 globalg,W,n,x,bestx,bestv,sum3 sum+=14 ifi>=n: #到達(dá)一個(gè)葉子結(jié)點(diǎn)5 ifcw<=Wandcv>bestv: #找到一個(gè)更優(yōu)解,保存它6 bestv=cv7 bestx=copy.deepcopy(x)8 else: #沒有到達(dá)葉子結(jié)點(diǎn)9 ifcw+g[i].w<=W:

#左剪支10 x[i]=1 #選取物品i11 dfs(cw+g[i].w,cv+g[i].v,i+1)12 b=bound(cw,cv,i+1) #計(jì)算限界函數(shù)值13 ifb>bestv:

#右剪支14 x[i]=0 #不選取物品i15 dfs(cw,cv,i+1)84/12617 defknap(g,W): #求0/1背包問題18 globaln,x,bestx,bestv,sum19 n=len(g) #物品個(gè)數(shù)20 x=[0]*n #解向量21 bestx=[0]*n #存放最優(yōu)解向量22 bestv=0 #存放最大價(jià)值,初始為023 sum=0 #累計(jì)搜索的結(jié)點(diǎn)個(gè)數(shù)24 print("求解結(jié)果")25 g.sort()26 dfs(0,0,0) #i從0開始27 foriinrange(0,n):28 ifbestx[i]==1:print("選取第%d個(gè)物品"%(g[i].no))29 print("總重量=%d,總價(jià)值=%d"%(W,bestv))30 print("sum=",sum)85/126【算法分析】上述算法在不考慮剪支時(shí)解空間樹中有2n+1-1個(gè)結(jié)點(diǎn)，求上界函數(shù)值和保存最優(yōu)解的時(shí)間為O(n)，所以最壞情況下算法的時(shí)間復(fù)雜度為O(n×2n)。程序驗(yàn)證86/126有n種重量和價(jià)值分別為wi、vi（0≤i<n）的物品，從這些物品中挑選總重量不超過W的物品，每種物品可以挑選任意多件，求挑選物品的最大價(jià)值。該問題稱為完全背包問題。5.2.4完全背包問題87/126解

與0/1背包問題不同，完全背包問題中物品i指的是第i種物品，每種物品可以取任意多件。對于解空間中第i層的結(jié)點(diǎn)，用cw、cv表示選擇物品的總重量和總價(jià)值，這樣處理物品i的方式如下：不選擇物品i。當(dāng)cw+w[i]≤W時(shí)，選擇物品i一件，下一步繼續(xù)選擇物品i。當(dāng)cw+w[i]≤W時(shí)，選擇物品i一件，下一步開始選擇物品i+1。3種選擇88/126n=2，W=2，w=（1，2），v=（2，5），結(jié)點(diǎn)對應(yīng)狀態(tài)是“(cw，cv，i)”，0,0,00,0,10,0,22,5,12,5,24,10,14,10,22,5,21,2,01,2,11,2,23,7,13,7,22,4,02,4,13,6,03,6,12,4,24,9,14,9,22,4,12,4,24,9,14,9,21,2,11,2,23,7,13,7,2不選擇物品i。選擇物品i一件，下一步繼續(xù)選擇物品i。選擇物品i一件，下一步開始選擇物品i+1。89/1261 defdfs(cw,cv,i): #回溯算法2 globalw,v,n,W,bestv3 ifi>=n:4 ifcw<=Wandcv>bestv: #找到一個(gè)更優(yōu)解5 bestv=cv6 else:7 dfs(cw,cv,i+1) #不選擇物品i8 ifcw+w[i]<=W:9 dfs(cw+w[i],cv+v[i],i) #剪支:選物品i,繼續(xù)選物品i10 ifcw+w[i]<=W:11 dfs(cw+w[i],cv+v[i],i+1) #剪支:選物品i,選下一件90/12613 defcompknap(w,v,n,W): #求解完全背包問題14 globalbestv15 bestv=0 #存放最大價(jià)值,初始為016 dfs(0,0,0)17 print("最大價(jià)值=",bestv)91/126程序驗(yàn)證intn=2;intw[]={1,2};intv[]={2,5};intW=2;92/126問題描述：在n×n（1≤n≤9）的方格棋盤上放置n個(gè)皇后，并且每個(gè)皇后不同行、不同列、不同左右對角線（否則稱為有沖突）。如下圖所示是6皇后問題的一個(gè)解。

設(shè)計(jì)一個(gè)算法求n個(gè)皇后的解個(gè)數(shù)，例如n=6時(shí)6皇后問題有4個(gè)解，因此返回結(jié)果為4。214365654321要求設(shè)計(jì)如下方法：def

totalNQueens(self,

n:

int)

->

int:5.3.9實(shí)戰(zhàn)—皇后Ⅱ（LeetCode52★★★）93/126解解空間是一棵子集樹（每個(gè)皇后在1～n列中找到一個(gè)適合的列號，即n選一），并且要求所有解。用整數(shù)數(shù)組q[N]存放n皇后的解，因?yàn)槊啃兄荒芊乓粋€(gè)皇后，q[i]（1≤i≤n）的值表示第i個(gè)皇后所在的列號。q[1..6]={2，4，6，1，3，5}21436565432194/126若在(i，j)位置上放第i個(gè)的皇后，是否與已放好的i-1個(gè)皇后(k，q[k])有沖突呢？如果(i，j)位置與前面某個(gè)皇后同列，則有q[k]==j成立。如果(i，j)位置與前面某個(gè)皇后同對角線，則恰好構(gòu)成一個(gè)等腰直角三角形，即有|q[k]-j|==|i-k|成立。歸納起來只要(i，j)位置滿足以下條件，則存在沖突，否則不沖突：(q[k]==j)||(abs(q[k]-j)==abs(i-k))

1≤k≤i-1沖突判斷q[k]-j(i，j)k-i(k，q[k])j-q[k]i-k(i，j)(k，q[k]（a）對角線1（b）對角線295/126求解皇后問題所有解的遞歸模型：queen(i，n)≡n個(gè)皇后放置完畢，輸出一個(gè)解

若i>nqueen(i，n)≡在第i行找到一個(gè)合適的位置(i，j)，

放置一個(gè)皇后; 其他 queen(i+1，n);96/1261 MAXN=20

#最多皇后個(gè)數(shù)2 q=[0]*MAXN

#q[i]存放第i個(gè)皇后的列號3 class

Solution:4

def

totalNQueens(self,

n:

int)

->

int:5

t=0

#累計(jì)解個(gè)數(shù)6

self.dfs(1,n)7

return

t97/1269

def

place(self,i,j):

#測試(i,j)位置能否放皇后10

if

i==1:

return

True

#第一個(gè)皇后總是可以放置11

k=112

while

k<i:

#k=1～i-1行已放置皇后13

if

q[k]==j

or

(abs(q[k]-j)==abs(i-k)):14

return

False15

k+=116

return

True沖突條件：

(q[k]==j)||(abs(q[k]-j)==abs(i-k))1≤k≤i-198/12618

def

dfs(self,i,n):

#回溯算法19

if

i>n:

#所有皇后放置結(jié)束20

t+=121

else:22

for

j

in

range(1,n+1):

#在第i行上試探每一個(gè)列j23

if

self.place(i,j):

#第i行找到合適位置(i,j)24

q[i]=j25

self.dfs(i+1,n)99/126每個(gè)皇后都要試探n列，共n個(gè)皇后，其解空間是一棵子集樹，每個(gè)結(jié)點(diǎn)可能有n棵子樹。每個(gè)皇后試探一個(gè)合適位置的時(shí)間為O(n)。所有算法的最壞時(shí)間復(fù)雜度為O(n×nn)。程序提交通過，執(zhí)行時(shí)間72ms，內(nèi)存消耗15MB。算法分析100/126問題描述：有n（n≥1）個(gè)任務(wù)需要分配給n個(gè)人執(zhí)行，每個(gè)任務(wù)只能分配給一個(gè)人，每個(gè)人只能執(zhí)行一個(gè)任務(wù)。第i個(gè)人執(zhí)行第j個(gè)任務(wù)的成本是c[i][j]（0≤i，j≤n-1）。求出總成本最小的一種分配方案。人員任務(wù)0任務(wù)1任務(wù)2任務(wù)309278164372581837694最小成本=135.3.10任務(wù)分配問題101/126解n個(gè)人和n個(gè)任務(wù)編號均用0～n-1表示。所謂一種分配方案就是由第i個(gè)人執(zhí)行第j個(gè)任務(wù)，每個(gè)人從n個(gè)任務(wù)中選擇一個(gè)任務(wù)，即n選一，所以本問題的解空間樹看成是一棵子集樹。求總成本最小解（最優(yōu)解是最小值），屬于求最優(yōu)解類型。用bestc表示最小成本，bestx為最優(yōu)分配方案。102/126used[j]=0xi=j表示人員i安排任務(wù)j第i層第i+1層第n層(葉子結(jié)點(diǎn))…解空間中根結(jié)點(diǎn)層次i為0，當(dāng)搜索到第i層每個(gè)結(jié)點(diǎn)時(shí)，表示為第i個(gè)人分配一個(gè)沒有分配的任務(wù)，即選擇滿足used[j]=0（0≤j≤n-1）的任務(wù)j。103/1263 defdfs1(cost,i): #回溯算法6 ifi>=n: #到達(dá)一個(gè)葉子結(jié)點(diǎn)7 ifcost<bestc: #比較求最優(yōu)解8 bestc=cost;bestx=copy.deepcopy(x)9 else:10 forjinrange(0,n): #為人員i試探任務(wù)j:0到n-111 ifused[j]:continue #跳過已經(jīng)分配的任務(wù)j12 used[j]=True13 x[i]=j #任務(wù)j分配給人員i14 cost+=c[i][j]15 dfs1(cost,i+1) #為人員i+1分配任務(wù)16 used[j]=False #回溯17 x[i]=-118 cost-=c[i][j]104/12620 defallocate1(c,n): #求解任務(wù)分配問題21 globalx,bestx,bestc,used,sum22 x=[0]*n23 bestx=[0]*n24 bestc=INF #初始化為∞25 used=[False]*n26 sum=027 dfs1(0,0) #從人員0開始28 print("求解結(jié)果")29 forkinrange(0,n):30 print("人員%d分配任務(wù)