回溯算法报告

实验四 回溯算法的应用

一、实验目的

1．掌握回溯算法的基本思想、技巧和效率分析方法。

2．熟练掌握用回溯算法求解问题的基本步骤，非递归算法框架和递归算法

框架。

3．学会利用回溯算法解决实际问题。

二、算法问题要求

任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。 注意：数字不能重复，N由键盘输入。

三、算法设计

有N件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

每个数的取法都有N个方向（1——N），当取够N个数时，输出一个排列，然后退后一步，取前一个数的下一个方向（即前一个数+1），并且要保证所有数字不能重复。当前数字的所有方向都取完时，继续退一步，一直重复到第一个数为止。

四、运行结果

五、程序

#include

void EnumList(char*, int, int);

int main(){

int iNum, i;

char szList[512];

printf(\输入全排的数字(1~N,N<=9):\\n\ scanf(\

for(i = 0; i < iNum; i++) szList[i] = i + 49; szList[i] = '\\0';

EnumList(szList, 0, i); return 0; };

void EnumList(char* CcList, int iBegin, int iEnd){

int i; char t;

if(iBegin < iEnd){

EnumList(CcList, iBegin + 1, iEnd); for(i = iBegin + 1; i < iEnd; i++){

t = CcList[iBegin];

CcList[iBegin] = CcList[i]; CcList[i] = t;

EnumList(CcList, iBegin + 1, iEnd); t = CcList[iBegin];

CcList[iBegin] = CcList[i]; CcList[i] = t; }; } else

printf(\};

六、总结

这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。 回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。