学习笔记2 | 算法设计 | 回溯法解决子集和问题

前言：关于本节的笔记，大多数是代码呈现，目前网上都是递归解决子集和问题，没有将剪枝的功能体现出来。希望本节笔记能帮助你了解回溯法的代码实现，子集和问题是我最近才遇见的，主要是代码的实现，很头大，特别是MATLAB，简直编的快炸了，也许是我太菜了-_-!

1.子集和问题

这是我算法课程学习时遇到的问题，简单来说，就是一个集合比如{2，2，4，6，5，5，7}，我现在给定一个目标值C，找出满足C的所有子集。

s=[2，2，4，6，5，5，7]

现在找出组合：

C = 10 = 2 + 2 + 6 =  4 + 6  =  5 + 5

而我们就是要通过回溯法找到如{2，2，4}和{5，5}这样的子集解。而这就是子集和问题。

2.回溯法

那么什么是回溯法，这个很好解释：

回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。

具体的概述本节不细讲，主要是代码实现：

3.C语言实现

代码里有详细解释，可以对照来看，基本原理就是一直递归并且进行剪枝，但是一定要先排序。

注意：回溯法求解的结果时全部解，只有分支限界法求的是一个可行解或者一个最优解。

#include <stdio.h> int sum=0; //sum是子集和问题的值和 int *s, *x, n,c;//c是目标值，n是子集的数值个数 注意：这里的指针有s和x，指代全局变量数组s和x int count = 0;//由count计数，count>0则表示有解 void bt(int i,int ts,int rs,int x[]) //当搜索到第i（ 1≤i≤n）的某个结点时，用ts表示选取的整数和，rs表示余下的整数和，即rs=s[i]+…+s[n]（其中包含s[i]） { if(i==n) { if(ts==c) //如果等于目标值 { printf("---结果：解%d---\n",count+1); for(i=0;i<n;i++) if(x[i]) printf("%3d",s[i]); printf("\n"); count++; } } else { //左剪枝：通过检查当前整数s[i]加入后子集和是否超过s，若是则剪枝，即仅仅扩展满足ts+s[i]≤c的左孩子结点。 //右剪枝：如果一个结点满足ts+rs-s[i]<c，也就是说即便选择剩余所有整数，也不可能找到一个解，即仅仅扩展满足ts+rs-s[i]≥c的右孩子结点。 if(ts+s[i]<=c)//左剪枝 { x[i]=1;//选择元素 printf("到达左！\n"); for(int d=0;d<n;d++) { if(x[d]) printf("%3d",s[d]); } printf("\n这时的rs的值：%d",rs); printf("\n"); bt(i+1,ts+s[i],rs-s[i],x); } if(ts+rs-s[i]>=c)//右剪枝 { x[i]=0;//不选择元素 printf("到达右！\n"); for(int d=0;d<n;d++) { if(x[d]) printf("%3d",s[d]); } printf("\n这时的rs的值：%d",rs); printf("\n"); bt(i+1,ts,rs-s[i],x); } } } int main() { int i; int exNum=0; printf("请输入子集个数n和目标值c：\n"); scanf("%d%d",&n,&c); //输入子集个数n，目标值c s=new int[n]; x=new int[n]; int l=0; //按照n的个数，循环录入到数组s和x里 for(i=0;i<n;i++){ l=i+1; printf("输入第%d个值：",l); scanf("%d",&s[i]); x[i]=0; } /* //测试用的数据 n=7; c=10; s=new int [n]; x=new int [n]; s[0]=2;s[1]=2;s[2]=4;s[3]=6;s[4]=5;s[5]=5;s[6]=7; i=n;*/ int rs=0; for(int f=0;f<n;f++) { x[f]=0; rs=rs+s[f]; } printf("排列前的子集：\n"); for(int q=0;q<i;q++) { printf("%d ",s[q]); } //排序：从小到大 for(int m=0;m<i;m++) { for(int n=m+1;n<i;n++) { if(s[m]>s[n]) { exNum=s[m]; s[m]=s[n]; s[n]=exNum; } } } printf("\n"); printf("排列后的子集：\n"); for(int w=0;w<i;w++) { printf("%d ",s[w]); } printf("\n"); //进入回溯函数 bt(0,sum,rs,x); if(count) printf("该子集有解！\n"); else printf("该子集无解！\n"); return 0; }

4.MATLAB实现

这个是目前我比较头大的，谁叫我才开始学习MATLAB-_-..........

4.1回溯递归剪枝函数m文件

这里面基本跟C语言的实现差别不大，可以对应C语言来看：

function count=bt(i,ts,rs,x,count,n,c,s) if(i==n) if(ts==c) count=count+1; str=['结果：解',num2str(count)]; disp(str); for i=1:n if(x(i)==1) disp(s(i)); end end end else if(ts+s(i)<=c) %左剪枝 x(i)=1; count=bt(i+1,ts+s(i),rs-s(i),x,count,n,c,s); end if(ts+rs-s(i)>=c) %右剪枝 x(i)=0; count=bt(i+1,ts,rs-s(i),x,count ,n,c,s); end end end

4.2主要m文件

%%子集和问题-回溯法 %比如 2 2 5 4 6 的目标值为10，结果就是 2 2 6 clear; clc; s=input('请输入集合的数值S(比如以矩阵形式输入[m,n,j,p...]):'); n=size(s,2); disp('该集合的大小N为：'); disp(n); c=input('请输入集合的目标值C:'); x=zeros(1,n); %生产一行为0大小为n的矩阵，储存值 sumn=0; %集合和的值，初值为0 rs=0; for f=1:n rs=rs+s(f); end s=sort(s); count=bt(1,sumn,rs,x,0,n,c,s); if(count>0) disp('该子集有解！'); else disp('该子集无解！'); end

结果

运行结果还是要有的，不然就是瞎说了：