Question

算法的子集和数问题

要求用1. 掌握回溯法解题的基本思想；
2. 掌握回溯算法的设计方法；
3. 针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。
4用算法来做

Answer 1

回溯算法设计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<stdio.h>
#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<n;i++)
printf("%2d",x[i]);
printf("\n");}

else if(((s+r)>=M)&&((s+w[k-1]+w[k]<=M)))
RecursiveSubset(s+w[k-1],r-w[k-1],k+1);
if((s+r-w[k-1]>=M)&&((s+w[k])<=M))
{x[k-1]=0;
RecursiveSubset(s,r-w[k-1],k+1);
}
}
void IterativeSubset(int m)/*针对问题实例的迭代回溯算法*/
{int i;
for(i=0;i<m;i++) x[i]=2;
for(i=k-1;i<n;i++) r+=w[i];
k=1;
while(k>0)
{--x[k-1];
if(x[k-1]==0)
{if((s+r-w[k-1]>=M)&&(s+w[k]<=M))
{s+=x[k-1]*w[k-1];
r-=w[k-1];
k++;
continue;
}
else{
--k;
s-=x[k-1]*w[k-1];
r+=w[k-1];
for(i=k;i<m-1;i++)
x[i]=2;
continue;
}
}
if(s+w[k-1]==M)
for(i=0;i<n;i++)
{printf("%2d",x[i]);}
else if((s+r>=M)&&(s+w[k-1]+w[k]<=M))
{s+=w[k-1];r-=w[k-1];k++;}
}
printf("\n");
}
void InitializeInstanse(void) /*问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r*/
{int i;
printf("Enter M:");
scanf("%d",&M);
for(i=0;i<n;i++)x[i]=0;
for(i=k-1;i<n;i++) r+=w[i];
for(i=0;i<k-2;i++) s+=x[i]*w[i];
}
main()
{InitializeInstanse();
RecursiveSubset(s,r,k);
IterativeSubset(n);
system("pause");

Answer 2

算法的子集和数问题

Answer 3

找不到啊 ， 等我知道了就告诉你啊。