当前位置:首页 >> 计算机软件及应用 >>

回溯算法


淮海工学院计算机工程学院 实验报告书
课 程 名 : 题 目: 《算法分析与设计》 实验 4 回溯算法

班 学 姓

级: 号: 名:

软件 142 2014122886 杨志远

评语:

成绩:

指导教师: 批阅时间: 年 月 日

《 算法分析与设计》实验报告

-1-

实验 4 回溯算法
实验目的和要求 (1)掌握回溯法的设计思想; (2)掌握解空间树的构造方法,以及在求解过程中如何存储求解路径; (3)考察回溯法求解问题的有效程度。 (4)设计可能解的表示方式,构成解空间树; (5)设计回溯算法完成问题求解; (6)设计测试数据,统计搜索空间的结点数; 实验内容 给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi,0/1 背包问题 ? ak 是如何选择装入背包的物品(物品不可分割),使得装入背包中物品的总价值最大? 实验环境 Turbo C 或 VC++ 实验学时 2 学时,必做实验 数据结构与算法
k ?i j

核心源代码

1、递归算法:
#include "stdio.h" #include "stdlib.h" #define m 10 int content=20; int n=6; int x[100]; int weight[m]={0,5,3,2,10,4,2}; int price[m]={0,11,8,15,18,12,6}; int currentWeight=0; int currentPrice=0; int bestPrice=0; int bestAnswer[m];

《 算法分析与设计》实验报告

-2-

void Print() { int i; for(i=1;i<n;i++) { printf("%d",x[i]); } printf("%d\t 最大价值为:%d\n",x[i],currentPrice); } void Backtracking(int i) { if(i>n) { Print(); if(currentPrice>bestPrice) { bestPrice=currentPrice; for(int j=1;j<=n;j++) { bestAnswer[j]=x[j]; } } return; } if(currentWeight+weight[i]<=content) { x[i]=1; currentWeight+=weight[i]; currentPrice+=price[i]; Backtracking(i+1); currentWeight-=weight[i]; currentPrice-=price[i];

《 算法分析与设计》实验报告

-3-

} x[i]=0; Backtracking(i+1); } int main() { Backtracking(1); printf("最优解为:"); for(int i=1;i<n;i++) { printf("%d",bestAnswer[i]); } printf("价值为:%d\n",bestPrice); return 0; }

2、迭代法:
# include <stdio.h> int content; //背包容量 int m; //物品数 int x[100]; int weight[100]; //物品重量 int price[100]; //物品价值 int bestprice=0; int bestAnswer[100]; //当前最优解 void beibestAnswero(int n) { int i,k; for (i=1; i<=n; i++) x[i]=0; k=1; while (k>=1) { //初始化

《 算法分析与设计》实验报告

-4-

x[k]=x[k]+1;

//第 k 个物品放入背包

if (x[k]<=2&& k==m) { //得到一个解,输出 int currentWeight=0; //当前重量 int currentPrice=0; //当前价值 for (i=1; i<=n; i++) { if(x[i]==1) { currentWeight += weight[i]; currentPrice += price[i]; } } if(currentWeight<=content) { if(currentPrice>bestprice) { bestprice=currentPrice; for (int j=1; j<=n; j++) { if(x[j]==2) bestAnswer[j]=x[j]-2; else bestAnswer[j]=x[j]; } } } } else if (x[k]<=2 && k<m) k=k+1; else //放置下一个物品

《 算法分析与设计》实验报告

-5-

{ x[k]=0; k=k-1; } } } //拿走第 k 个物品,重置 x[k],回溯

void main() { int i; printf("请输入物品的数量:"); scanf("%d",&m); printf("请输入背包的容量:"); scanf("%d",&content); printf("请依次输入%d 个物品的重量:",m); for(i=1;i<=m;i++) scanf("%d",&weight[i]); printf("请依次输入%d 个物品的价值:",m); for(i=1;i<=m;i++) scanf("%d",&price[i]); beibestAnswero(m); printf("\n 最优解为"); for(i=1;i<m;++i) printf("%d,",bestAnswer[i]); printf("%d}\t 背包获得的最大价值为:%d\n",bestAnswer[i],bestprice); }

《 算法分析与设计》实验报告

-6-

实验结果

1、递归算法:

2、迭代法:

实验体会
通过这次实验我了解了回溯法的基本思想,从解空间树深度优先策略搜素满足约束条件的解。 在搜索至树中的某结点时, 先判断该结点对应的部分解是否满足约束条件, 如果肯定不包含最优解, 则跳过该结点为根的子树,否则进入该结点为根的子树,继续按照深度优先策略进行搜索。 算法分析对于我来说还是有一定的难度的。不仅需要理解各个方法的基本思想和解题思路,还 要将所学知识运用到编程当中去。在编程过程中,我会遇到很多问题,这让我体会到了还需巩固以 前所学的编程知识,否则很难实现问题的解决。


相关文章:
回溯算法的应用
回溯算法的应用_计算机软件及应用_IT/计算机_专业资料。回溯算法的应用回溯算法的应用 课程名称: 院系: 算法设计与分析 *** *** *** 学生姓名: 学号: 专业班...
算法设计与分析:回溯法-实验报告
算法设计与分析:回溯法-实验报告 - 应用数学 学院 姓名 实验题目 信息安全 专业 班 学号 回溯算法 实验评分表 序 评分项目 号 1 指导教师评分标准 完成度 评分...
搜索与回溯算法
搜索与回溯算法 - 搜索与回溯算法 回溯算法 ......
回溯算法实例一
回溯算法实例一 - 【问题】 填字游戏 问题描述: 在 3×3 个方格的方阵中要填入数字 1 到 N (N≥10) 内的某 9 个数字, 每个方格填一个整数,使得所有...
c语言经典算法回溯法
c语言经典算法回溯法 - c 语言经典算法 五、回溯回溯法也称为试探法, 该方法首先暂时放弃关于问题规模大小的限制, 并将问题的候选解按 某种顺序逐一枚举和...
回溯算法实验报告
回溯算法实验报告_调查/报告_表格/模板_实用文档。回溯算法实验报告一、问题定义 在 n*n 格的棋盘上放置彼此不受攻击的 n 个皇后。按照国际象棋的规矩,皇后 ...
算法期末复习题
算法期末复习题 - 1、二分搜索算法是利用( A、分治策略 A )实现的算法。 C、贪心法 A D、回溯法 )。 D、定义最优解 B、动态规划法 2、下列不是动态...
回溯算法实验
回溯算法实验 - 算法设计分析实验: 素数环问题和n皇后问题... 回溯算法实验_计算机软件及应用_IT/计算机_专业资料。算法设计分析实验: 素数环问题和n皇后问题 ...
算法--回溯法
算法--回溯法 - 实验报告(2016/2017 学年 第二学期) 课程名称 实验名称 实验时间 指导单位 指导教师 2017 算法分析与设计 回溯法 年 5 月 24 日...
01背包问题回溯算法
01背包问题回溯算法 - 假设有 7 个物品,它们的重量和价值如下表所示。若这些物品均不能 被分割,且背包容量 M=150,使用回溯方法求解此背包问题。请写 出状态...
更多相关标签: