子集和數問題——回溯法（C++）

問題描述
已知(w1, w2, …, wn)和M，均爲正數。要求找出wi的和數等於M的全部子集。web

例如：若n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31，則知足要求的子集是(11,13,7)和(24,7).算法

分析數組

子集和數問題解的一種表示方法svg

• 解由n-元組(x1, x2, …, xn)表示;
• 顯式約束條件xi∈{0,1}，1≤i≤n，若是沒有選擇Wi，則xi=0；若是選擇了Wi，則xi=1。因而上面的解能夠表示爲(1，1，0，1)和(0,0,1,1);
• 隱式約束條件(xi× wi)的和數爲M
• 解空間的大小爲2n個元組

#include<stdio.h>
// 宏定義最大個數MAX
#define MAX 10000
// 設置集合個數
int data[MAX] ;
// 是否選擇該元素（True或False）對應與data集合的映射v
bool v[MAX] ;
// 集合元素的個數n，用戶輸入的子集和目標值c
int n , c ;


// 回溯函數traceback
bool traceback(int n)
{ 
 
  
// p能夠當作是一個指針pointer，或者更準確來講應該是一個遊標
// 做爲咱們[1]數組data和[2]data數組映射子集選中數組v的[遊標]
// sum是當前正在跑着的子集的和的值

// 對p和sum進行初始化
// 注：p是遊標，在C語言中，數組元素下標默認從0開始
int p = 0 ,sum = 0 ;

// 判斷當前遊標的位置
// 遊標位置p<0則退出循環
while(p>=0)
{ 
 
  
/* 選擇新進來的元素 */
// 當v[p]==0進入循環
if(!v[p])
{ 
 
  
// 子集中選中v[p]
v[p] = true ;
// 計算子集和，在sum上進行累加data[p]
sum += data[p] ;

// 判斷當前累加的子集和sum和目標子集和c
// 若是相等
if(c == sum)
// 返回true
// 找到子集和的解
return true ;

// 若是當前累加的子集和sum > 目標值c
else if( c < sum)
{ 
 
  
// 不選擇當前的a[p]值(重置v[p]爲False)
// 並在當前子集和sum的基礎上減去加上的a[p]
v[p] = false ;
sum -=data[p] ;
}
// 移動遊標到下一位
p++ ;
}


/* 回溯過程(到最後一個元素都未找到解進入) */
// 檢查遊標位置p是否跑完數組data集合全部n個元素
// 若是當前遊標值p大於等於集合數組data的元素個數n則進入回溯過程
if(p>=n)
{ 
 
  
// 到最後一個元素還沒加到c，sum<c
// 最後一個元素爲True
// 回溯到上次爲False的地方在從新開始
while( v[p-1] )
{ 
 
  
// p遊標自減
p-- ;
// 對當前v[p]賦值
v[p] = false ;
// 跑完整個data數組的n個元素
if(p<1) return false ;
}
//0 1 0 1 0 0 0 1

// 到最後一個元素sum>c
// 最後一個元素爲False
// 回溯到上次爲Ture的地方在從新開始
while( !v[p-1])
{ 
 
  
p-- ;
if(p<1) return false ;
}

// 回溯過程當前子集和sum也回溯到上次
sum -= data[p-1] ;
// 同時對當前回溯的v[p]重置爲false(至關於不要這個元素)
v[p-1] = false ;
}
}

// 找不到知足子集和目標值的子集和解
// 退出回溯函數
return false ;
}

// 主函數
int main()
{ 
 
  
// 讀入集合元素個數n，子集和目標值c
scanf("%d %d" , &n , &c) ;
// 依次讀入集合中的n個元素
for(int i = 0 ; i < n ; i++)
scanf("%d" , &data[i]) ;

// 用回溯法計算子集和
// 判斷是否存在結果(存在即traceback的值爲True)
// 輸出結果
if(traceback(n))
{ 
 
  
// traceback函數返回值爲true
// 則獲得目標值子集和的解
// 輸出函數結果


int first = 1 ;
// i遍歷v，範圍是[0, n)，即整個集合data數組以及數組v
for(int i = 0 ; i < n; i++)
// 判斷v中第(i+1)個元素(v[i])的值是否爲0(是否被選中爲子集中的元素)
if(v[i])
{ 
 
  
// v[i]被選中了做爲子集和中的元素

// first的值爲非0
if(first)
// first變量重置爲0
first = 1;
// first的值爲0
else
printf(" ") ;
printf("%d " , data[i]) ;
}
printf("\n") ;
}
// traceback函數返回值爲False
// 沒法獲得該目標值子集和的解
else
printf("No Solution!\n") ;

return 0 ;
}

引伸

1、子集樹函數

**子集樹：**當所給的問題是從n個元素的集合S中找出知足某種性質的子集時，相應的解空間稱爲子集樹。spa

例如，那個物品的0-1揹包問題所相應的解空間樹就是一顆子集樹。這類子集問題一般有2^n
個葉節點，其節點總個數爲2^{(n+1)-1。遍歷子集樹的任何算法均須要O(2}n)的計算時間。
指針

void backtrack (int t)  
{ 
 
    
if (t>n) output(x);  
else  
for (int i=0;i<=1;i++) { 
 
    
x[t]=i;  
if (legal(t)) backtrack(t+1);  
}  
}

2、排列樹
排列樹：當所給問題是肯定n個元素知足某種性質的排列時，相應的解空間樹稱爲排列樹。code

排列樹一般有n!個葉子節點。所以遍歷排列樹須要O(n!)的計算時間。
xml

void backtrack (int t)  
{ 
 
    
if (t>n) output(x);  
else  
for (int i=t;i<=n;i++) { 
 
    
swap(x[t], x[i]);  
if (legal(t)) backtrack(t+1);  
swap(x[t], x[i]);  
}  
}