窮舉搜索法
窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，并從眾找出那些符合要求的候選解作為問題的解。
【問題】 將A、B、C、D、E、F這六個變量排成如圖所示的三角形，這六個變量分別取[1，6]上的整數，且均不相同。求使三角形三條邊上的變量之和相等的全部解。如圖就是一個解。
程序引入變量a、b、c、d、e、f，并讓它們分別順序取1至6的證書，在它們互不相同的條件下，測試由它們排成的如圖所示的三角形三條邊上的變量之和是否相等，如相等即為一種滿足要求的排列，把它們輸出。當這些變量取盡所有的組合后，程序就可得到全部可能的解。細節見下面的程序。
【程序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”);
- }
- }
- }
- }
- }
- }
對一組數窮盡所有排列，還有更直接的方法。將一個排列看作一個長整數，則所有排列對應著一組整數。將這組整數按從小到大的順序排列排成一個整數，從對應最小的整數開始。按數列的遞增順序逐一列舉每個排列對應的每個整數，這能更有效地完成排列的窮舉。從一個排列找出對應數列的下一個排列可在當前排列的基礎上作部分調整來實現。倘若當前排列為1，2，4，6，5，3，并令其對應的長整數為124653。要尋找比長整數124653更大的排列，可從該排列的最后一個數字順序向前逐位考察，當發現排列中的某個數字比它前一個數字大時，如本例中的6比它的前一位數字4大，這說明還有對應更大整數的排列。但為了順序從小到大列舉出所有的排列，不能立即調整得太大，如本例中將數字6與數字4交換得到的排列126453就不是排列124653的下一個排列。為了得到排列124653的下一個排列，應從已經考察過的那部分數字中選出比數字大，但又是它們中最小的那一個數字，比如數字5，與數字4交換。該數字也是從后向前考察過程中第一個比4大的數字。5與4交換后，得到排列125643。在前面數字1，2，5固定的情況下，還應選擇對應最小整數的那個排列，為此還需將后面那部分數字的排列順序顛倒，如將數字6，4，3的排列順序顛倒，得到排列1，2，5，3，4，6，這才是排列1，2，4，6，5，3的下一個排列。按以上想法編寫的程序如下。
【程序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; }
- }
- }
【問題】 背包問題
問題描述：有不同價值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。
設n個物品的重量和價值分別存儲于數組w[ ]和v[ ]中，限制重量為tw?？紤]一個n元組（x0，x1，…，xn-1），其中xi=0 表示第i個物品沒有選取，而xi=1則表示第i個物品被選取。顯然這個n元組等價于一個選擇方案。用枚舉法解決背包問題，需要枚舉所有的選取方案，而根據上述方法，我們只要枚舉所有的n元組，就可以得到問題的解。
顯然，每個分量取值為0或1的n元組的個數共為2n個。而每個n元組其實對應了一個長度為n的二進制數，且這些二進制數的取值范圍為0～2n-1。因此，如果把0～2n-1分別轉化為相應的二進制數，則可以得到我們所需要的2n個n元組。
【算法】- maxv=0;
- for (i=0;i<2n;i++)
- { B[0..n-1]=0;
- 把i轉化為二進制數，存儲于數組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數組；
- }
- }
- }
|