学习常用算法之(3)回溯法(续)
【问题】 组合问题
问题描述:找出从自然数 1,2,…,n 中任取 r 个数的所有组合。
采用回溯法找问题的解,将找到的组合以从小到大顺序存于 a[0],a[1],…,a[r-1]中,组
合的元素满足以下性质:
(1) a[i+1]>a[i],后一个数字比前一个大;
(2) a[i]-i<=n-r+1。
按回溯法的思想,找解过程可以叙述如下:
首先放弃组合数个数为 r 的条件,候选组合从只有一个数字 1 开始。因该候选解满足除问
题规模之外的全部条件,扩大其规模,并使其满足上述条件( 1),候选组合改为 1,2。
继续这一过程,得到候选组合 1,2,3。该候选解满足包括问题规模在内的全部条件,因
而是一个解。在该解的基础上,选下一个候选解,因 a[2]上的 3 调整为 4,以及以后调整为
5 都满足问题的全部要求,得到解 1,2,4 和 1,2,5。由于对 5 不能再作调整,就要从
a[2]回溯到 a[1],这时,a[1]=2,可以调整为 3,并向前试探,得到解 1,3,4。重复上述向
前试探和向后回溯,直至要从 a[0]再回溯时,说明已经找完问题的全部解。按上述思想写
成程序如下:
public class TestComb{
public static void main(String args[]){
comb(6,3);
}
public static void comb(int m,int r){
int i=0,j;
int a[]=new int[100];
a[i]=1;
do {
if (a[i]-i<=m-r+1)/*还能向前试探*/
{ if(i==r-1)/*已经找到一个可行的组合解*/
{ for (j=0;j< r;j++)
System.out.printf("%4d",a[j]);
System.out.println();
a[i]++;/*调整*/
continue;
}
i++;/*扩展,向前试探*/
a[i]=a[i-1]+1;
}
else/*不能试探,理应回溯*/
{ if (i==0) /找到所有可行的解,结束*/
评论0