算法的子集和数问题

[大学生女生节各学院活动点子集锦]09传播6班 “难易忘记初次见你，一双迷人的眼睛……”女生节的前一天晚上东十四楼下的09传播6班全体男生嘹亮的歌声打破夜深的寂静，引起该宿舍女生的骚动。再加上...+阅读

回溯算法设计2008-05-29 10:15 P.M.[实验目的] 1. 掌握回溯法解题的基本思想； 2. 掌握回溯算法的设计方法； 3. 针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。 [预习要求] 1. 认真阅读教材或参考书，掌握回溯法解题的基本思想，算法的抽象控制策略； 2. 了解子集和数问题及解向量的定长和变长状态空间表示； 3. 针对解向量的定长表示，设计状态空间树节点扩展的规范（限界）函数及实现方法； 4. 分析深度优先扩展状态空间树节点或回溯的条件； 5. 分析和设计生成解向量各分量可选值的实现方法； 6. 设计和编制回溯算法的递归和迭代程序。

[参考数据类型或变量] float s； // 表示有可能抵达答案节点的子路径上的元素之和； float r； // 尚未测试的剩余集合元素之和； float w[n]； // 存储原始集合的n个元素，根据问题实例初始化； int x[n]； // 定长表示的解向量，各元素初始值为0； [参考子程序接口与功能描述] void RecursiveSubset(float s, float r, int k) 功能：针对问题实例的递归回溯算法。

void IterativeSubset(int m) 功能：针对问题实例的迭代回溯算法。 void InitializeInstanse(void) 功能：问题实例的初始化函数，初始化子集和数M , w, x向量， s, r。 [实验步骤] 1. 录入、修改并测试你的程序，直至正确为止； 2. 针对问题实例，实录运行时的输入、输出界面； 3. 将你的程序和实录的界面存盘备用。 [实验报告要求] 1. 阐述实验目的和实验内容； 2. 提交模块化的实验程序源代码； 3. 简述程序的测试过程，提交实录的输入、输出界面； 4. 鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。

[思考与练习] 1. 试针对解向量的变长表示设计回溯算法，上机测试正确性。 2. 试针对0/1背包问题设计回溯算法，比较与子集和数问题的算法差异。 #include#define n 3 float s； /*表示有可能抵达答案节点的子路径上的元素之和；*/ float r； /*尚未测试的剩余集合元素之和；*/ float w[n]={2,3,4}； /*存储原始集合的n个元素，根据问题实例初始化；*/ int x[n]； /*定长表示的解向量，各元素初始值为0;*/ int M; int k; void RecursiveSubset(float s, float r, int k)/*针对问题实例的递归回溯算法*/ {int i; x[k-1]=1; if(s+w[k-1]==M) {for(i=0;i=M)&((s+w[k-1]+w[k]=M)&((s+w[k])