窮舉搜索法
窮舉搜索法是對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問(wèn)題的解。
【問(wèn)題】 將A、B、C、D、E、F這六個(gè)變量排成如圖所示的三角形，這六個(gè)變量分別取[1，6]上的整數(shù)，且均不相同。求使三角形三條邊上的變量之和相等的全部解。如圖就是一個(gè)解。
程序引入變量a、b、c、d、e、f，并讓它們分別順序取1至6的證書(shū)，在它們互不相同的條件下，測(cè)試由它們排成的如圖所示的三角形三條邊上的變量之和是否相等，如相等即為一種滿足要求的排列，把它們輸出。當(dāng)這些變量取盡所有的組合后，程序就可得到全部可能的解。細(xì)節(jié)見(jiàn)下面的程序。
【程序1】- # include <stdio.h>
- void main()
- { int a,b,c,d,e,f;
- for (a=1;a<=6;a++)
- for (b=1;b<=6;b++) {
- if (b==a) continue;
- for (c=1;c<=6;c++) {
- if (c==a)||(c==b) continue;
- for (d=1;d<=6;d++) {
- if (d==a)||(d==b)||(d==c) continue;
- for (e=1;e<=6;e++) {
- if (e==a)||(e==b)||(e==c)||(e==d) continue;
- f=21-(a+b+c+d+e);
- if ((a+b+c==c+d+e))&&(a+b+c==e+f+a)) {
- printf(“%6d,a);
- printf(“%4d%4d”,b,f);
- printf(“%2d%4d%4d”,c,d,e);
- scanf(“%*c”);
- }
- }
- }
- }
- }
- }
對(duì)一組數(shù)窮盡所有排列，還有更直接的方法。將一個(gè)排列看作一個(gè)長(zhǎng)整數(shù)，則所有排列對(duì)應(yīng)著一組整數(shù)。將這組整數(shù)按從小到大的順序排列排成一個(gè)整數(shù)，從對(duì)應(yīng)最小的整數(shù)開(kāi)始。按數(shù)列的遞增順序逐一列舉每個(gè)排列對(duì)應(yīng)的每個(gè)整數(shù)，這能更有效地完成排列的窮舉。從一個(gè)排列找出對(duì)應(yīng)數(shù)列的下一個(gè)排列可在當(dāng)前排列的基礎(chǔ)上作部分調(diào)整來(lái)實(shí)現(xiàn)。倘若當(dāng)前排列為1，2，4，6，5，3，并令其對(duì)應(yīng)的長(zhǎng)整數(shù)為124653。要尋找比長(zhǎng)整數(shù)124653更大的排列，可從該排列的最后一個(gè)數(shù)字順序向前逐位考察，當(dāng)發(fā)現(xiàn)排列中的某個(gè)數(shù)字比它前一個(gè)數(shù)字大時(shí)，如本例中的6比它的前一位數(shù)字4大，這說(shuō)明還有對(duì)應(yīng)更大整數(shù)的排列。但為了順序從小到大列舉出所有的排列，不能立即調(diào)整得太大，如本例中將數(shù)字6與數(shù)字4交換得到的排列126453就不是排列124653的下一個(gè)排列。為了得到排列124653的下一個(gè)排列，應(yīng)從已經(jīng)考察過(guò)的那部分?jǐn)?shù)字中選出比數(shù)字大，但又是它們中最小的那一個(gè)數(shù)字，比如數(shù)字5，與數(shù)字4交換。該數(shù)字也是從后向前考察過(guò)程中第一個(gè)比4大的數(shù)字。5與4交換后，得到排列125643。在前面數(shù)字1，2，5固定的情況下，還應(yīng)選擇對(duì)應(yīng)最小整數(shù)的那個(gè)排列，為此還需將后面那部分?jǐn)?shù)字的排列順序顛倒，如將數(shù)字6，4，3的排列順序顛倒，得到排列1，2，5，3，4，6，這才是排列1，2，4，6，5，3的下一個(gè)排列。按以上想法編寫(xiě)的程序如下。
【程序2】- # include <stdio.h>
- # define SIDE_N 3
- # define LENGTH 3
- # define VARIABLES 6
- int A,B,C,D,E,F;
- int *pt[]={&A,&B,&C,&D,&E,&F};
- int *side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,&A};
- int side_total[SIDE_N];
- main{}
- { int i,j,t,equal;
- for (j=0;j<VARIABLES;j++)
- *pt[j]=j+1;
- while(1)
- { for (i=0;i<SIDE_N;i++)
- { for (t=j=0;j<LENGTH;j++)
- t+=*side[i][j];
- side_total[i]=t;
- }
- for (equal=1,i=0;equal&&i<SIDE_N-1;i++)
- if (side_total[i]!=side_total[i+1] equal=0;
- if (equal)
- { for (i=1;i<VARIABLES;i++)
- printf(“%4d”,*pt[i]);
- printf(“\n”);
- scanf(“%*c”);
- }
- for (j=VARIABLES-1;j>0;j--)
- if (*pt[j]>*pt[j-1]) break;
- if (j==0) break;
- for (i=VARIABLES-1;i>=j;i--)
- if (*pt[i]>*pt[i-1]) break;
- t=*pt[j-1];* pt[j-1] =* pt[i]; *pt[i]=t;
- for (i=VARIABLES-1;i>j;i--,j++)
- { t=*pt[j]; *pt[j] =* pt[i]; *pt[i]=t; }
- }
- }
【問(wèn)題】 背包問(wèn)題
問(wèn)題描述：有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過(guò)指定的限制重量，但選中物品的價(jià)值之和最大。
設(shè)n個(gè)物品的重量和價(jià)值分別存儲(chǔ)于數(shù)組w[ ]和v[ ]中，限制重量為tw。考慮一個(gè)n元組（x0，x1，…，xn-1），其中xi=0 表示第i個(gè)物品沒(méi)有選取，而xi=1則表示第i個(gè)物品被選取。顯然這個(gè)n元組等價(jià)于一個(gè)選擇方案。用枚舉法解決背包問(wèn)題，需要枚舉所有的選取方案，而根據(jù)上述方法，我們只要枚舉所有的n元組，就可以得到問(wèn)題的解。
顯然，每個(gè)分量取值為0或1的n元組的個(gè)數(shù)共為2n個(gè)。而每個(gè)n元組其實(shí)對(duì)應(yīng)了一個(gè)長(zhǎng)度為n的二進(jìn)制數(shù)，且這些二進(jìn)制數(shù)的取值范圍為0～2n-1。因此，如果把0～2n-1分別轉(zhuǎn)化為相應(yīng)的二進(jìn)制數(shù)，則可以得到我們所需要的2n個(gè)n元組。
【算法】- maxv=0;
- for (i=0;i<2n;i++)
- { B[0..n-1]=0;
- 把i轉(zhuǎn)化為二進(jìn)制數(shù)，存儲(chǔ)于數(shù)組B中;
- temp_w=0;
- temp_v=0;
- for (j=0;j<n;j++)
- { if (B[j]==1)
- { temp_w=temp_w+w[j];
- temp_v=temp_v+v[j];
- }
- if ((temp_w<=tw)&&(temp_v>maxv))
- { maxv=temp_v;
- 保存該B數(shù)組；
- }
- }
- }
|