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

回溯算法

淮海工学院计算机工程学院 实验报告书
课 程 名 : 题 目: 《算法分析与设计》 实验 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、迭代法:

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


相关文章:
回溯与分支限界算法设计 - 百度文库
回溯与分支限界算法设计 - 算法设计与分析实验报告专业姓名 实验名称 实验目的 班级学号 实验四:回溯与分支限界算法设计 1.掌握回溯法解决问题的一般步骤。 2...
算法设计与分析:回溯法-实验报告
算法设计与分析:回溯法-实验报告 - 应用数学 学院 姓名 实验题目 信息安全 专业 班 学号 回溯算法 实验评分表 序 评分项目 号 1 指导教师评分标准 完成度 评分...
回溯算法实例一
回溯算法实例一 - 【问题】 填字游戏 问题描述: 在 3×3 个方格的方阵中要填入数字 1 到 N (N≥10) 内的某 9 个数字, 每个方格填一个整数,使得所有...
c语言经典算法回溯法
c语言经典算法回溯法 - c 语言经典算法 五、回溯回溯法也称为试探法, 该方法首先暂时放弃关于问题规模大小的限制, 并将问题的候选解按 某种顺序逐一枚举和...
最佳调度问题 回溯算法分析
最佳调度问题 回溯算法分析 - 《算法设计与分析》上机报告 姓名: 张先荣 学号: SA16225439 日期: 2016/12/20 上机题 实验七:最佳调度问题(回溯算法) 目: 实验...
回溯算法(C++版)
回溯算法(C++版) - 一、回溯算法的定义: 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是: 从一条路往前走,能进则进,不能进...
回溯算法的应用
回溯算法的应用_计算机软件及应用_IT/计算机_专业资料。回溯算法的应用回溯算法的应用 课程名称: 院系: 算法设计与分析 *** *** *** 学生姓名: 学号: 专业班...
回溯算法实验
回溯算法实验 - 算法设计分析实验: 素数环问题和n皇后问题... 回溯算法实验_计算机软件及应用_IT/计算机_专业资料。算法设计分析实验: 素数环问题和n皇后问题 ...
算法设计与分析--回溯法
算法设计与分析--回溯法 - 回溯算法的应用 课程名称: 院系: 算法设计与分析 学生姓名: 学号: 专业班级: 指导教师: 2013 年 12 月 27 日 回溯算法的应用 ....
lab6_回溯算法设计与应用
lab6_回溯算法设计与应用 - 实验六 回溯算法设计与应用 一.基本原理的概括 DFS+剪枝(在状态空间树上作带剪枝的 DFS 搜索)?剪枝:若搜索到某结点,其对应 的部...
更多相关标签: