子集和數(shù)的回溯算法

1、設(shè)計(jì)四子集和數(shù)的回溯算法班級(jí)通信08-2BF 學(xué)號(hào)1408230929 姓名楊福成績分一、設(shè)計(jì)目的1. 掌握回溯法解題的基本思想；2. 掌握子集和數(shù)問題的回溯算法；3. 進(jìn)一步掌握子集和數(shù)問題的回溯遞歸算法、迭代算法的基本思想和算法設(shè)計(jì)方法；二、設(shè)計(jì)內(nèi)容a)任務(wù)描述1) 子集和數(shù)問題簡介子集和數(shù)問題是假定有n個(gè)不同的正數(shù)(通常稱為權(quán))，要求找出這些數(shù)中所有事的某和數(shù)為M的組合。2) 設(shè)計(jì)任務(wù)簡介設(shè)計(jì)、編程、測試 求解子集和數(shù)問題的回溯算法。1. 子集和數(shù)問題的表示方案本設(shè)計(jì)利用大小固定的元組來研究回溯算法，在此情況下，解向量的元素 X (i)取 1或0值，它表示是否包含了權(quán)數(shù)W (i).生成圖

2、中任一結(jié)點(diǎn)的兒子是很容易的。對(duì)于i級(jí)上的一個(gè)結(jié)點(diǎn)，其左兒子對(duì)應(yīng)于X (i) =1 ,右兒子對(duì)應(yīng)于 X(i)=0。對(duì)于限界函數(shù)的kn一種簡單選擇是， 當(dāng)且僅當(dāng) £ W (i)X (i)十£ W (i)芝M 時(shí)，B(X(1), 七X (k) )=true。 i 云i d< 1顯然，如果這個(gè)條件不滿足，X(1), ，X (k)就不能導(dǎo)致一個(gè)答案結(jié)點(diǎn)。如果假定這些 W (i) 一開始就是按非降次序列排列的，那么這些限界函數(shù)可以被強(qiáng)化。在這種情k況下，如果 £ W(i)X (i) +W(k +1)M，則X(1), ，X (k)就不能導(dǎo)致一個(gè)答案結(jié) i ±點(diǎn)。

3、因 此，將要使用 的限界函數(shù)是 B k (X ( 1 ),，X ( k) =true,當(dāng)且僅當(dāng)，W(i)X (i) + £ W (i) =M 。 i :i 吐 12. 主要數(shù)據(jù)類型與變量int M ;/表示要求得到的子集和；int s; /表示所選當(dāng)前元素之前所選的元素和；int wN;/存儲(chǔ)原始集合的N個(gè)元素，根據(jù)問題實(shí)例初始化;int xN;/變長表示的解向量，不進(jìn)行初始化；3. 算法或程序模塊#include<stdio.h>#define M 31#define N 4 /集合元素個(gè)數(shù)int wN=11,13,24,7;int xN;void Subset(int

4、 s,int k) /解子集和數(shù)問題函數(shù)int i,l;l=0; xl=k;while(l>=0)while(s+wxl-1<M&&k<=N)s=s+wxl-1;k+;l+;xl=k;while(s+wxl-1>M&&k<=N)k+;xl=k;if(s+wxl-1=M)k+;for(i=0;i<=l;i+)printf(" %d",xi);/輸出變長解向量 printf("n");while(k>N) 返回上一個(gè)節(jié)點(diǎn),實(shí)現(xiàn)回溯的主要思想l-;k=xl;xl=k+1;s=0;for(i=0;i<l;i+)s=s+wxi-1;void main()Subset(0,1);/倜用 subset(int s,int k)®數(shù)、測試4. 方案在VC6.0中進(jìn)行編譯、運(yùn)行以上程序，編譯正確，運(yùn)行正常。5. 結(jié)果運(yùn)行結(jié)果符合設(shè)計(jì)要求，達(dá)到預(yù)期的效果。三、總結(jié)與討論這種列式使用大小固定的元組表示所有的解，得出一個(gè)問題的解可以有數(shù)種表示形式，而這些表示形式都是的所有的解是滿足某些約束條