子集和数回溯算法

《子集和数回溯算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、设计四子集和数的回溯算法班级通信08-2BF学号1408230929姓名杨福成绩分一、设计目的1.掌握回溯法解题的基本思想；2.掌握子集和数问题的回溯算法；3.进一步掌握子集和数问题的回溯递归算法、迭代算法的基本思想和算法设计方法；二、设计内容a)任务描述1）子集和数问题简介子集和数问题是假定有n个不同的正数（通常称为权），要求找出这些数中所有事的某和数为M的组合。2）设计任务简介设计、编程、测试求解子集和数问题的回溯算法。1．子集和数问题的表示方案本设计利用大小固定的元组来研究回溯算法，在此情况下，解向量的元素X（i）取1或0值，它表示是否包含了权数W（

2、i）.生成图中任一结点的儿子是很容易的。对于i级上的一个结点，其左儿子对应于X（i）=1，右儿子对应于X(i)=0。对于限界函数的一种简单选择是，当且仅当时，B(X(1),···，X（k）)=true。显然，如果这个条件不满足，X(1),···，X（k）就不能导致一个答案结点。如果假定这些W（i）一开始就是按非降次序列排列的，那么这些限界函数可以被强化。在这种情况下，如果,则X(1),···，X（k）就不能导致一个答案结点。因此，将要使用的限界函数是B（X（1），···，X（k））=true,当且仅当。2．主要数据类型与变量intM;//表示要求得到的子集

3、和；ints;//表示所选当前元素之前所选的元素和；intw[N];//存储原始集合的N个元素,根据问题实例初始化；intx[N];//变长表示的解向量,不进行初始化；1．算法或程序模块#include#defineM31#defineN4//集合元素个数intw[N]={11,13,24,7};intx[N];voidSubset(ints,intk)//解子集和数问题函数{inti,l;l=0;x[l]=k;while(l>=0){while(s+w[x[l]-1]

4、]=k;}while(s+w[x[l]-1]>M&&k<=N){k++;x[l]=k;}if(s+w[x[l]-1]==M){k++;for(i=0;i<=l;i++)printf("%d",x[i]);//输出变长解向量printf("");}while(k>N)//返回上一个节点，实现回溯的主要思想{l--;k=x[l];x[l]=k+1;s=0;for(i=0;i

5、运行以上程序，编译正确，运行正常。2．结果运行结果符合设计要求，达到预期的效果。一、总结与讨论这种列式使用大小固定的元组表示所有的解，得出一个问题的解可以有数种表示形式，而这些表示形式都是的所有的解是满足某些约束条件的多元组。回溯算法通过系统的检索给定问题的解空间来确定问题的解。这检索可以用这个解空间的树结构来简化。对于一个给定的解空间，可能有多种树结构。