搜索與回溯算法CPPT課件

1、 搜索與回溯是計算機解題中常用的算法，很多問題無法根據(jù)某種確定的計算法則來求解，可以利用搜索與回溯的技術求解。回溯是搜索算法中的一種控制策略。它的基本思想是：為了求得問題的解，先選擇某一種可能情況向前探索，在探索過程中，一旦發(fā)現(xiàn)原來的選擇是錯誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復進行，直至得到解或證明無解。 如迷宮問題：進入迷宮后，先隨意選擇一個前進方向，一步步向前試探前進,如果碰到死胡同，說明前進方向已無路可走，這時，首先看其它方向是否還有路可走，如果有路可走，則沿該方向再向前試探；如果已無路可走，則返回一步，再看其它方向是否還有路可走；如果有路可走，則沿該方向再向前試探。按此原則

2、不斷搜索回溯再搜索，直到找到新的出路或從原路返回入口處無解為止。第1頁/共45頁遞歸回溯法算法框架一int Search(int k)for (i=1;i=算符種數(shù);i+)if (滿足條件) 保存結果if (到目的地) 輸出解; else Search(k+1);恢復：保存結果之前的狀態(tài)回溯一步 遞歸回溯法算法框架二int Search(int k) if (到目的地) 輸出解;elsefor (i=1;i=算符種數(shù);i+)if (滿足條件) 保存結果; Search(k+1);恢復：保存結果之前的狀態(tài)回溯一步第2頁/共45頁【例1】素數(shù)環(huán):從1到20這20個數(shù)擺成一個環(huán)，要求相鄰的兩個數(shù)的和

3、是一個素數(shù)?！舅惴ǚ治觥?非常明顯，這是一道回溯的題目。從1開始，每個空位有20種可能，只要填進去的數(shù)合法：與前面的數(shù)不相同；與左邊相鄰的數(shù)的和是一個素數(shù)。第20個數(shù)還要判斷和第1個數(shù)的和是否素數(shù)?！舅惴鞒獭?、數(shù)據(jù)初始化； 2、遞歸填數(shù)：判斷第i個數(shù)填入是否合法；A、如果合法：填數(shù)；判斷是否到達目標（20個已填完）：是，打印結果；不是，遞歸填下一個；B、如果不合法：選擇下一種可能；【參考程序】#include#include#include#includeusing namespace std;bool b21=0;int total=0,a21=0;int search(int); /回

4、溯過程int print(); /輸出方案bool pd(int,int); /判斷素數(shù) 第3頁/共45頁int main() search(1); couttotalendl; /輸出總方案數(shù) system(pause);int search(int t) int i; for (i=1;i=20;i+) /有20個數(shù)可選 if (pd(at-1,i)&(!bi) /判斷與前一個數(shù)是否構成素數(shù)及該數(shù)是否可用 at=i; bi=1; if (t=20) if (pd(a20,a1) print(); else search(t+1); bi=0; int print() total+; cou

5、ttotal; for (int j=1;j=20;j+) coutaj ; coutendl; bool pd(int x,int y) int k=2,i=x+y; while (ksqrt(i) return 1; else return 0;第4頁/共45頁【例2】設有n個整數(shù)的集合1,2,n，從中取出任意r個數(shù)進行排列（rn），試列出所有的排列。#include#include#includeusing namespace std;int num=0,a10001=0,n,r;bool b10001=0;int search(int); /回溯過程int print(); /輸出方案

6、int main() coutnr; search(1); coutnumber=numendl; /輸出方案總數(shù)第5頁/共45頁int search(int k) int i; for (i=1;i=n;i+) if (!bi) /判斷i是否可用 ak=i; /保存結果 bi=1; if (k=r) print(); else search(k+1); bi=0; int print() num+; for (int i=1;i=r;i+) coutsetw(3)ai; coutendl; 第6頁/共45頁【例3】任何一個大于1的自然數(shù)n，總可以拆分成若干個小于n的自然數(shù)之和。當n=7共14

7、種拆分方法：7=1+1+1+1+1+1+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1+2+27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+4total=14第7頁/共45頁【參考程序】#include#include#includeusing namespace std;int a10001=1,n,total;int search(int,int);int print(int);int main() cinn; search(n,1); /將要拆分的數(shù)n傳遞給s couttotal

8、=totalendl; /輸出拆分的方案數(shù) system(pause);int search(int s,int t) int i; for (i=at-1;i=s;i+) if (i0時，繼續(xù)遞歸 s+=i; /回溯：加上拆分的數(shù)，以便產(chǎn)分所有可能的拆分 int print(int t) coutn=; for (int i=1;i=t-1;i+) /輸出一種拆分方案 coutai+; coutatendl; total+; /方案數(shù)累加1第8頁/共45頁【例4】八皇后問題：要在國際象棋棋盤中放八個皇后，使任意兩個皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一對角線的任意棋子。）放置

9、第個(行)皇后的算法為：int search(i)； int j;for (第i個皇后的位置j=1;j=8;j+ ) /在本行的8列中去試if (本行本列允許放置皇后)放置第i個皇后； 對放置皇后的位置進行標記；if (i=8) 輸出 /已經(jīng)放完個皇后 else search(i+1)； /放置第i+1個皇后對放置皇后的位置釋放標記，嘗試下一個位置是否可行；第9頁/共45頁【算法分析】 顯然問題的關鍵在于如何判定某個皇后所在的行、列、斜線上是否有別的皇后；可以從矩陣的特點上找到規(guī)律，如果在同一行，則行號相同；如果在同一列上，則列號相同；如果同在 斜線上的行列值之和相同；如果同在 斜線上的行列值

10、之差相同；從下圖可驗證： 考慮每行有且僅有一個皇后，設一維數(shù)組1.8表示皇后的放置：第行皇后放在第列，用ij來表示，即下標是行數(shù)，內(nèi)容是列數(shù)。例如：A3=5就表示第3個皇后在第3行第5列上。第10頁/共45頁 判斷皇后是否安全，即檢查同一列、同一對角線是否已有皇后，建立標志數(shù)組1.8控制同一列只能有一個皇后，若兩皇后在同一對角線上，則其行列坐標之和或行列坐標之差相等，故亦可建立標志數(shù)組1.16、-7.7控制同一對角線上只能有一個皇后。 如果斜線不分方向，則同一斜線上兩皇后的行號之差的絕對值與列號之差的絕對值相同。在這種方式下，要表示兩個皇后I和J不在同一列或斜線上的條件可以描述為：AIAJ A

11、ND ABS(I-J)ABS(AI-AJ)I和J分別表示兩個皇后的行號【參考程序】#include#include#include#includeusing namespace std;bool d100=0,b100=0,c100=0;int sum=0,a100;int search(int);int print();int main() search(1); /從第1個皇后開始放置 system(pause);第11頁/共45頁int search(int i) int j; for (j=1;j=8;j+) /每個皇后都有8位置(列)可以試放if (!bj)&(!ci+j)&(!di-

12、j+7) /尋找放置皇后的位置 /由于C+不能操作負數(shù)組，因此考慮加7 /放置皇后,建立相應標志值 ai=j; /擺放皇后 bj=1; /宣布占領第j列 ci+j=1; /占領兩個對角線 di-j+7=1; if (i=8) print(); /個皇后都放置好,輸出 else search(i+1); /繼續(xù)遞歸放置下一個皇后 bj=0; /遞歸返回即為回溯一步,當前皇后退出 ci+j=0; di-j+7=0; int print() int i; sum+; /方案數(shù)累加1 coutsum=sumendl; for (i=1;i=8;i+) /輸出一種方案 coutsetw(4)ai; co

13、ut2,1-3,3-1,4-3,5-2,7-4,8【算法分析】 如圖4（b）,馬最多有四個方向，若原來的橫坐標為j、縱坐標為i,則四個方向的移動可表示為：1: （i,j）（i+2,j+1）； (i3,j8)2: （i,j）（i+1,j+2）； (i4,j0,j1,j8) 搜索策略： S1:=(0,0); S2:從1出發(fā)，按移動規(guī)則依次選定某個方向，如果達到的是（4,8）則轉向S3,否則繼續(xù)搜索下一個到達的頂點； S3:打印路徑。第13頁/共45頁【參考程序】#include#include#includeusing namespace std;int a100100,t=0; /路徑總數(shù)和路徑

14、int x4=2,1,-1,-2, /四種移動規(guī)則 y4=1,2,2,1;int search(int); /搜索 int print(int); /打印int main() /主程序 a11=0;a12=0; /從坐標(0,0)開始往右跳第二步 search(2); system(pause); 第14頁/共45頁int search(int i) for (int j=0;j=0&ai-11+xj=0&ai-12+yj=8) /判斷馬不越界 ai1=ai-11+xj; /保存當前馬的位置 ai2=ai-12+yj; if (ai1=4&ai2=8) print(i); else searc

15、h(i+1); /搜索下一步 int print(int ii) t+; coutt: ; for (int i=1;i=ii-1;i+) coutai1,ai2; cout4,8endl; 第15頁/共45頁【例6】設有A，B，C，D，E五人從事J1，J2，J3，J4，J5五項工作，每人只能從事一項，他們的效益如下。 每人選擇五項工作中的一項，在各種選擇的組合中，找到效益最高的的一種組合輸出?！舅惴ǚ治觥?用數(shù)組儲存工作選擇的方案；數(shù)組存放最優(yōu)的工作選擇方案；數(shù)組用于表示某項工作有沒有被選擇了。 (1)選擇(i)=0的第i項工作； (2)判斷效益是否高于max已記錄的效益，若高于則更新數(shù)組及

16、max的值。 搜索策略: 回溯法（深度優(yōu)先搜索dfs）。第16頁/共45頁【參考程序】#include#include#include#includeusing namespace std;int data66=0,0,0,0,0,0,0,13,11,10,4,7,0,13,10,10,8,5,0,5,9,7,7,4,0,15,12,10,11,5,0,10,11,8,8,4;int max1=0,g10,f10;bool p6=0;int go(int step,int t) / step是第幾個人，t是之前已得的效益 for (int i=1;i=5;i+) if (!pi) /判斷第i項

17、工作沒人選擇 fstep=i; /第step個人，就選第i項工作 pi=1; /標記第i項工作被人安排了 t+=datastepi; /計算效益值 if (stepmax1) /保存最佳效益值 max1=t; for (int j=1;j=5;j+) gj=fj; /保存最優(yōu)效益下的工作選擇方案 t-=datastepi; /回溯 pi=0; 第17頁/共45頁int main() go(1,0); /從第1個人，總效益為0開始 for (int i=1;i=5;i+) coutchar(64+i):Jgisetw(3); /輸出各項工作安排情況 coutendl; coutsupply:ma

18、x1endl; /輸出最佳效益值第18頁/共45頁【例7】選書 學校放寒假時，信息學競賽輔導老師有A，B，C，D，E五本書，要分給參加培訓的張、王、劉、孫、李五位同學，每人只能選一本書。老師事先讓每個人將自己喜歡的書填寫在如下的表格中。然后根據(jù)他們填寫的表來分配書本，希望設計一個程序幫助老師求出所有可能的分配方案，使每個學生都滿意?！舅惴ǚ治觥?可用窮舉法，先不考慮“每人都滿意” 這一條件，這樣只?！懊咳诉x一本且只能選一本”這一條件。在這個條件下，可行解就是五本書的所有全排列，一共有5！=120種。然后在120種可行解中一一刪去不符合“每人都滿意”的解，留下的就是本題的解答。 為了編程方便，設

19、1，2，3，4，5分別表示這五本書。這五個數(shù)的一種全排列就是五本書的一種分發(fā)。例如54321就表示第5本書（即E）分給張，第4本書（即D）分給王，第1本書（即A）分給李。“喜愛書表”可以用二維數(shù)組來表示，1表示喜愛，0表示不喜愛。第19頁/共45頁算法設計：S1：產(chǎn)生5個數(shù)字的一個全排列； S2：檢查是否符合“喜愛書表”的條件，如果符合就打印出來； S3：檢查是否所有的排列都產(chǎn)生了，如果沒有產(chǎn)生完，則返回S1； S4：結束。int Search(i) for (j=1;j=5;j+) if (第i個同學分給第j本書符合條件) 記錄第i個數(shù) if (i=5) 打印一個解; else Search

20、(i+1); 刪去第i 個數(shù) 上述算法有可以改進的地方。比如產(chǎn)生了一個全排列12345，從表中可以看出，選第一本書即給張同學的書，1是不可能的，因為張只喜歡第3、4本書。這就是說，1一類的分法都不符合條件。由此想到，如果選定第一本書后，就立即檢查一下是否符合條件，發(fā)現(xiàn)1是不符合的，后面的四個數(shù)字就不必選了，這樣就減少了運算量。換句話說，第一個數(shù)字只在3、4中選擇，這樣就可以減少3/5的運算量。同理，選定了第一個數(shù)字后，也不應該把其他4個數(shù)字一次選定，而是選擇了第二個數(shù)字后，就立即檢查是否符合條件。例如，第一個數(shù)選3，第二個數(shù)選4后，立即檢查，發(fā)現(xiàn)不符合條件，就應另選第二個數(shù)。這樣就把34一類的

21、分法在產(chǎn)生前就刪去了。又減少了一部分運算量。 綜上所述，改進后的算法應該是：在產(chǎn)生排列時，每增加一個數(shù)，就檢查該數(shù)是否符合條件，不符合，就立刻換一個，符合條件后，再產(chǎn)生下一個數(shù)。因為從第I本書到第I+1本書的尋找過程是相同的，所以可以用回溯算法。算法設計如下：第20頁/共45頁【參考程序】#include#include#includeusing namespace std;int book6,c;bool flag6,like66=0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,1, 0,0,1,1,0,0,0,0,0,0,1,0,0,0,1,0,0,1;int sear

22、ch(int);int print();int main() for (int i=1;i=5;i+) flagi=1; search(1); /從第1個開始選書，遞歸。 system(pause); int search(int i) /遞歸函數(shù) for (int j=1;j=5; j+) /每個人都有5本書可選 if (flagj&likeij) /滿足分書的條件 flagj=0; /把被選中的書放入集合flag中，避免重復被選 booki=j; /保存第i個人選中的第j本書 if (i=5) print(); /i=5時，所有的人都分到書，輸出結果 else search(i+1); /

23、i5時，繼續(xù)遞歸分書 flagj=1; /回溯：把選中的書放回，產(chǎn)生其他分書的方案 booki=0; 第21頁/共45頁int print() c+; /方案數(shù)累加1 cout answer c :n; for (int i=1;i=5;i+) cout i : char(64+booki) endl; /輸出分書的方案輸出結果：zhang: Cwang: Aliu: Bsun: Dli: E第22頁/共45頁【例8】跳馬問題。在5*5格的棋盤上，有一只中國象棋的馬，從（1,1）點出發(fā)，按日字跳馬，它可以朝8個方向跳，但不允許出界或跳到已跳過的格子上，要求在跳遍整個棋盤。輸出前5個方案及總方案

24、數(shù)。輸出格式示例：1 16 21 10 2520 11 24 15 2217 2 19 6 912 7 4 23 143 18 13 8 5#include#include#include#includeusing namespace std;int u8=1,2,2,1,-1,-2,-2,-1, /8個方向上的x,y增量 v8=-2,-1,1,2,2,1,-1,-2;int a100100=0,num=0; /記每一步走在棋盤的哪一格和棋盤的每一格有 /沒有被走過bool b100100=0;int search(int,int,int); /以每一格為階段，在每一階段中試遍8個方向int

25、print(); /打印方案第23頁/共45頁int main() a11=1;b11=1; /從(1,1)第一步開始走 search(1,1,2); /從(1,1)開始搜第2步該怎樣走 coutnum25) print();return 0; /達到最大規(guī)模打印、統(tǒng)計方案 for (k=0;k=7;k+) /試遍8個方向 x=i+uk;y=j+vk; /走此方向，得到的新坐標 if (x=1&y=1&(!bxy) /如果新坐標在棋盤上，并且這一格可以走 bxy=1; axy=n; search(x,y,n+1); /從(x,y)去搜下一步該如何走 bxy=0; axy=0; 第24頁/共45

26、頁int print() num+; /統(tǒng)計總方案 if (num=5) /打印出前5種方案 for (int k=1;k=5;k+) /打印本次方案 for (int kk=1;kk=5;kk+) coutsetw(5)akkk; coutendl; 第25頁/共45頁【例9】數(shù)的劃分(NOIP2001)【問題描述】 將整數(shù)n分成k份，且每份不能為空，任意兩種分法不能相同(不考慮順序)。例如:n=7,k=3,下面三種分法被認為是相同的。 1，1，5； 1，5，1； 5，1，1； 問有多少種不同的分法。 【輸入格式】 n,k (6n200，2k6) 【輸出格式】 一個整數(shù)，即不同的分法。 【輸

27、入樣例】 7 3 【輸出樣例】 4 4種分法為：1,1,5；1,2,4；1,3,3; 2,2,3 說明部分不必輸出 第26頁/共45頁【算法分析】 方法1、回溯法，超時，參考程序如下。#include#include#includeusing namespace std;int n,i,j,k,rest,sum,total;int s7;int main() cout n k; total = 0; s1 = 0; i = 1; while (i) si+; if (si n) i-; else if (i = k) sum = 0; for ( j = 1; j = k; j+) sum +

28、= s j; if (n = sum) total+; else rest -= si; i+; si = si-1 - 1; cout total; system(pause); return 0;第27頁/共45頁 方法2、遞歸，參考程序如下。 #include #include #include using namespace std; int n,k; int f(int a,int b,int c) int g = 0,i; if (b = 1) g = 1; else for (i = c; i = a/b; i+) g += f(a-i,b-1,i); return g; int

29、 main() cout n k; cout f(n,k,1); system(pause); return 0; 第28頁/共45頁 方法3、用動態(tài)循環(huán)窮舉所有不同的分解，要注意剪枝，參考程序如下。#include#include#includeusing namespace std;int n,k,total;int min(int x,int y) if (x = rest/dep; i-) select(dep-1,rest-i,i);int main() cout n k; total = 0; select(k,n,n); cout total; system(pause); re

30、turn 0;第29頁/共45頁 方法4、遞推法 首先將正整數(shù)n分解成k個正整數(shù)之和的不同分解方案總數(shù)等于將正整數(shù)n-k分解成任意個不大于k的正整數(shù)之和的不同分解方案總數(shù)(可用ferror圖證明之),后者的遞推公式不難得到,參考程序如下。 #include #include #include #include using namespace std; int i,j,k,n,x; int p2017; int main() cin n k; memset(p,0,sizeof(p); p00 = 1; for (i = 1; i = n; i+) pi1 = 1; for (i = 1; i

31、= n - k; i+) for ( j = 2; j = min(i,k); j+) for (x = 1; x = min(i,j); x+) pi j += pi-xmin(i-x,x); cout pn-kk; system(pause); return 0; 第30頁/共45頁【課堂練習】 1、輸出自然數(shù)1到n所有不重復的排列，即n的全排列?！緟⒖歼^程】 int Search(int i) Int j; for (j=1;j=n;j+) if (bj) ai=j; bj=false; if (In) Search(i+1); else print(); bj=true; 第31頁/共

32、45頁2、找出n個自然數(shù)(1,2,3,n)中r個數(shù)的組合。例如，當n=,r=3時，所有組合為：1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5total=10 /組合的總數(shù)【分析】：設在b1,b2,bi-1中已固定地取了某一組值且bi-1=k的前提下，過程Search(i,k)能夠列出所有可能的組合。由于此時bi只能取k+1至n-r+i，對j=k+1,k+2,n-r+i，使bi:=j，再調(diào)用過程Search(i+1,j)，形成遞歸調(diào)用。直至i的值大于r時，就可以在b中構成一種組合并輸出。第32頁/共45頁3、輸出字母a、b、c、d，4個元素全

33、排列的每一種排列。4、顯示從前m個大寫英文字母中取n個不同字母的所有種排列。5、有A、B、C、D、E五本書，要分給張、王、劉、趙、錢五位同學，每人只能選一本，事先讓每人把自已喜愛的書填于下表，編程找出讓每人都滿意的所有方案?！敬鸢浮克姆N方案張 王 劉 趙 錢 C A B D E D A C B E D B C A E D E C A B第33頁/共45頁6、有紅球4個，白球3個，黃球3個，將它們排成一排共有多少種排法？【分析】：可以用回溯法來生成所有的排法。用數(shù)組b1.3表示尚未排列的這3種顏色球的個數(shù)。設共有I-1個球已參加排列，用子程序Search(i)生成由第I個位置開始的以后n-I+1

34、位置上的各種排列。對于第I個位置，我們對3種顏色的球逐一試探，看每種顏色是否還有未加入排序的球。若有，則選取一個放在第I個位置上，且將這種球所剩的個數(shù)減1，然后調(diào)用Search(I+1),直至形成一種排列后出。對第I個位置上的所有顏色全部試探完后，則回溯至前一位置。第34頁/共45頁【上機練習】1、全排列問題(Form.cpp)【問題描述】 輸出自然數(shù)1到n所有不重復的排列，即n的全排列，要求所產(chǎn)生的任一數(shù)字序列中不允許出現(xiàn)重復的數(shù)字?！据斎敫袷健?n(1n9)【輸出格式】 由1n組成的所有不重復的數(shù)字序列，每行一個序列。【輸入樣例】Form.in 3【輸出樣例】Form.out1 2 31

35、3 22 1 32 3 13 1 23 2 1第35頁/共45頁2、組合的輸出(Compages.cpp)【問題描述】 排列與組合是常用的數(shù)學方法，其中組合就是從n個元素中抽出r個元素(不分順序且rn)，我們可以簡單地將n個元素理解為自然數(shù)1，2，n，從中任取r個數(shù)。 現(xiàn)要求你用遞歸的方法輸出所有組合。 例如n5，r3，所有組合為： l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5【輸入】 一行兩個自然數(shù)n、r(1n21，1rn)?！据敵觥?所有的組合，每一個組合占一行且其中的元素按由小到大的順序排列，每個元素占三個字符的位

36、置，所有的組合也按字典順序?！緲永縞ompages.in compages.out5 3 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5第36頁/共45頁3、N皇后問題(Queen.cpp)【問題描述】在N*N的棋盤上放置N個皇后（n=10）而彼此不受攻擊（即在棋盤的任一行，任一列和任一對角線上不能放置2個皇后），編程求解所有的擺放方法。八皇后的兩組解【輸入格式】 輸入：n【輸出格式】每行輸出一種方案，每種方案順序輸出皇后所在的列號，各個數(shù)之間有空格隔開。若無方案，則輸出no solute!【輸入樣例】Queen.in

37、4【輸出樣例】Queen.out2 4 1 33 1 4 2第37頁/共45頁4、有重復元素的排列問題【問題描述】 設R= r1, r2 , , rn是要進行排列的n個元素。其中元素r1, r2 , , rn可能相同。試設計一個算法，列出R的所有不同排列。【編程任務】 給定n 以及待排列的n 個元素。計算出這n 個元素的所有不同排列?！据斎敫袷健?由perm.in輸入數(shù)據(jù)。文件的第1 行是元素個數(shù)n，1n500。接下來的1 行是待排列的n個元素?！据敵龈袷健?計算出的n個元素的所有不同排列輸出到文件perm.out中。文件最后1行中的數(shù)是排列總數(shù)?！据斎霕永?aacc【輸出樣例】多解aacc

38、acacaccacaaccacaccaa6第38頁/共45頁5、子集和問題【問題描述】 子集和問題的一個實例為S,t。其中，S= x1， x2， xn是一個正整數(shù)的集合，c是一個正整數(shù)。子集和問題判定是否存在S的一個子集S1，使得子集S1和等于c?！揪幊倘蝿铡?對于給定的正整數(shù)的集合S= x1， x2， xn和正整數(shù)c，編程計算S 的一個子集S1，使得子集S1和等于c?！据斎敫袷健?由文件subsum.in提供輸入數(shù)據(jù)。文件第1行有2個正整數(shù)n和c，n表示S的個數(shù)，c是子集和的目標值。接下來的1 行中，有n個正整數(shù)，表示集合S中的元素?！据敵龈袷健?程序運行結束時，將子集和問題的解輸出到文件s

39、ubsum.out中。當問題無解時，輸出“No solution!”?！据斎霕永? 102 2 6 5 4【輸出樣例】2 2 6第39頁/共45頁6、工作分配問題【問題描述】 設有n件工作分配給n個人。將工作i分配給第j個人所需的費用為cij。試設計一個算法，為每一個人都分配一件不同的工作，并使總費用達到最小?！揪幊倘蝿铡?設計一個算法，對于給定的工作費用，計算最佳工作分配方案，使總費用達到最小?！据斎敫袷健?由文件job.in給出輸入數(shù)據(jù)。第一行有1個正整數(shù)n (1n20)。接下來的n行，每行n個數(shù)，第i行表示第i個人各項工作費用?！据敵龈袷健?將計算出的最小總費用輸出到文件job.out?！据斎霕永?4 2 52 3 63 4 5【輸出樣例】9第40頁/共45頁7、裝載問題