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

回溯算法

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

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


相关文章:
回溯算法原理和几个常用的算法实例.doc
IT技术| 算法| 回溯算法原理和几个常用的算法实例_IT/计算机_专业资料。回溯算法,八皇后问题,迷宫问题,骑士周游问题,幂集问题的算法原理和程序 回溯...
回溯算法_图文.ppt
回溯算法_学科竞赛_高中教育_教育专区。回溯算法2016冬令营第4讲 1 ?
回溯算法(一)_图文.ppt
回溯算法(一) - 回溯算法(一) 重庆教育学院 杨华千 回溯算法:一般方法 ?
深度优先搜索与回溯算法_图文.ppt
深度优先搜索与回溯算法 - 深度优先搜索与回溯算法 回溯是计算机解题中常用的算法
回溯算法的一些例题.doc
回溯算法的一些例题 - 回溯算法 搜索与回溯是计算机解题中常用的算法, 很多问题
回溯算法的应用.doc
回溯算法的应用_计算机软件及应用_IT/计算机_专业资料。回溯算法的应用回溯算法的应用 课程名称: 院系: 算法设计与分析 *** *** *** 学生姓名: 学号: 专业班...
递归与回溯算法_图文.ppt
递归与回溯算法 - 递归的定义 所谓递归就是一个函数或过程可以直接或间接地调用自
第5章 搜索与回溯算法(C++版)_图文.ppt
第5章 搜索与回溯算法(C++版) - 超级好的资料,保证是精品文档... 第五章 搜索与回溯算法 搜索与回溯是计算机解题中常用的算法,很多问题无法根据 某种确定的计算法...
回溯算法实例一.doc
回溯算法实例一 - 【问题】 填字游戏 问题描述: 在 3×3 个方格的方阵中要
回溯算法(一).doc
回溯算法(一) - 第一部分 回溯 寻找问题的解的一种可靠的方法是首先列出所有候
算法设计与分析:回溯法-实验报告.doc
算法设计与分析:回溯法-实验报告 - 应用数学 学院 姓名 实验题目 信息安全 专业 班 学号 回溯算法 实验评分表 序 评分项目 号 1 指导教师评分标准 完成度 评分...
最佳调度问题 回溯算法分析.doc
最佳调度问题 回溯算法分析 - 《算法设计与分析》上机报告 姓名: 张先荣 学号: SA16225439 日期: 2016/12/20 上机题 实验七:最佳调度问题(回溯算法) 目: 实验...
c语言经典算法回溯法.doc
c语言经典算法回溯法 - c 语言经典算法 五、回溯回溯法也称为试探法, 该
子集和数的回溯算法.doc
子集和数的回溯算法 - 设计四 子集和数的回溯算法 班级通信 08-2BF 学号
回溯算法_图文.pdf
回溯算法 - 第 7章 7.1 回溯法的思想方法 问题的解可用一个n元数组x=(
实验六 回溯算法.doc
实验六 回溯算法 - 实验六 回溯算法(2 学时) 一、实验目的与要求 1、掌握装载问题的回溯算法; 2、初步掌握回溯算法; 二、实验题 有一批共 n 个集装箱要装...
回溯算法(C++版).doc
回溯算法(C++版) - 一、回溯算法的定义: 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是: 从一条路往前走,能进则进,不能进...
回溯算法.doc
回溯算法 算法算法隐藏>> 第4 章 回溯 寻找问题的解的一种可靠的
回溯算法的应用(DOC).doc
回溯算法的应用(DOC) - 回溯算法的应用 课程名称: 院系: 算法设计与分析
搜索与回溯算法C版_图文.ppt
搜索与回溯算法C版 - 搜索与回溯是计算机解题中常用的算法,很多问题无法根据 某
更多相关标签: