当前位置:首页 >> IT/计算机 >>

回溯算法


背包回溯算法 背包回溯算法 班级:10 级通信二班 学号:14102303001 姓名:蔡诚 成绩 分

一、设计目的 (1)掌握回溯法的设计思想; (2)掌握解空间树的构造方法,以及在求解过程中如何存储求解路径; (3)考察回溯法求解问题的有效程度。 (4)设计可能解的表示方式,构成解空间树; (5)设计回溯算法完成问题求解; (6)设计测试数据,统计搜索空间的结点数; 二、设计内容 1. . 任务描述 给定 n 种物品和一个容量为 C 的背包, 物品 i 的重量是 wi, 其价

值为 vi,0/1 背包问题是如何选择装入背包的物品(物品不可分割) ,使得 装入背包中物品的总价值最大。 2. . 背包回溯的表示方案 背包回溯的表示方案

X1*X2=Y(Max) ( ) 递推过程的抽象描述 本设计采用前向或后向递推公式。用自然语言、伪程序设计语言或流程图 等形式针对快速贪心的求解(抽象地)描述递推过程…… 3. . 主要数据类型与变量

int c; //背包容量 int m; //物品数 int x[100]; int weight[100]; //物品重量 int price[100]; //物品价值 int bp=0; int bA[100]; //当前最优解 int times=0; for (i=1; i<=n; i++) x[i]=0; 三、测试 //初始化

四、总结与讨论 通过这次试验,我掌握了回溯法的设计思想,如何构造解空间树,如 何储存求解路径。 递归的思想: (1) 考虑物品 i 被选择,这种可能性仅当包含它不会超过方 案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。 (2) 考虑物品 i 不被选择,这种可能性仅当不包含物品 i 也有可能会找 到价值更大的方案的情况。 迭代的思想:对物品 i 的考察有这样几种情况:当该物品被包含在候选解 中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑 的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当 物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选 解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前 候选解中的方案也不应继续考虑。

附:程序模块的源代码 # include <stdio.h>

int c; //背包容量 int m; //物品数 int x[100]; int weight[100]; //物品重量

int price[100]; //物品价值 int bp=0; int bA[100]; //当前最优解 int times=0;

void beibao(int n) { int i,k; for (i=1; i<=n; i++) x[i]=0; k=1; while (k>=1) { times+=1; 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<=c) { if(currentPrice>bp) { bp=currentPrice; for (int j=1; j<=n; j++) { if(x[j]==2) bA[j]=x[j]-2; else

bA[j]=x[j]; } } } } else if (x[k]<=2 && k<m) k=k+1; else { x[k]=0; k=k-1; } } } //拿走第 k 个物品,重置 x[k],回溯 //放置下一个物品

void main() { int i; /*输入部分*/

printf("请输入物品的数量:\n"); scanf("%d",&m); printf("请输入背包的容量(能承受的重量):\n"); scanf("%d",&c); printf("请依次输入%d 个物品的重量:\n",m); for(i=1;i<=m;i++) scanf("%d",&weight[i]); printf("请依次输入%d 个物品的价值:\n",m); for(i=1;i<=m;i++) scanf("%d",&price[i]); beibao(m); printf("************************************************** *****\n"); printf("\nthe best answer is {"); for(i=1;i<m;++i) printf("%d,",bA[i]); printf("%d}\tthe price is %d\n",bA[i],bp); printf("\n\n 总共搜索结点数%d\n",times); }


相关文章:
回溯算法原理和几个常用的算法实例.doc
IT技术| 算法| 回溯算法原理和几个常用的算法实例_IT/计算机_专业资料。回溯算法,八皇后问题,迷宫问题,骑士周游问题,幂集问题的算法原理和程序 回溯...
深度优先搜索与回溯算法_图文.ppt
深度优先搜索与回溯算法 - 深度优先搜索与回溯算法 回溯是计算机解题中常用的算法
回溯算法_图文.ppt
回溯算法_学科竞赛_高中教育_教育专区。回溯算法2016冬令营第4讲 1 ?
算法分析_回溯法(很不错).ppt
? 回溯法回溯算法是所有搜索算法中最为基本的一种算法,是一 种能避免不必要搜索的
回溯算法的应用.doc
回溯算法的应用_计算机软件及应用_IT/计算机_专业资料。回溯算法的应用回溯算法的应用 课程名称: 院系: 算法设计与分析 *** *** *** 学生姓名: 学号: 专业班...
回溯算法实例一.doc
回溯算法实例一 - 【问题】 填字游戏 问题描述: 在 3×3 个方格的方阵中要
算法设计与分析--回溯法.doc
算法设计与分析--回溯法 - 回溯算法的应用 课程名称: 院系: 算法设计与分析 学生姓名: 学号: 专业班级: 指导教师: 2013 年 12 月 27 日 回溯算法的应用 ....
回溯算法实验.doc
回溯算法实验 - 算法设计分析实验: 素数环问题和n皇后问题... 回溯算法实验
【精品】回溯算法pascal_图文.ppt
【精品】回溯算法pascal - 回溯法 深度优先探索-DFS 回溯算法思想:
C语言回溯算法_图文.ppt
回溯算法:假设问题的解的形式为(x1,x2,x3,……..xn),x1∈S1,
回溯算法(含代码).doc
回溯算法(含代码) - 回溯算法 引言 寻找问题的解的一种可靠的方法是首先列出所
第5章 搜索与回溯算法(C++版)_图文.ppt
第5章 搜索与回溯算法(C++版) - 超级好的资料,保证是精品文档... 第五章 搜索与回溯算法 搜索与回溯是计算机解题中常用的算法,很多问题无法根据 某种确定的计算法...
浅谈回溯算法_图文.ppt
浅谈回溯算法 - 第五讲 回溯算法 从问题的某一种可能出发, 搜索从这种情况出发
哈密顿回路问题的回溯算法.doc
哈密顿回路问题的回溯算法 - ● 哈密顿回路问题: ● 解空间: A={ (x1
回溯算法_图文.ppt
回溯算法 - 回溯算法 奥赛暑假培训班专题之一 双十中学 庄晓芳 2006.7 回溯算法是所有搜索算法中最为基本的一种算法,是一种 能避免不必要搜索的穷举式的搜索...
回溯算法(一)_图文.ppt
回溯算法(一) - 回溯算法(一) 重庆教育学院 杨华千 回溯算法:一般方法 ?
搜索与回溯算法.doc
搜索与回溯算法 - 搜索与回溯算法 回溯算法 ......
Pascal回溯算法.doc
Pascal回溯算法 - 第二节 回溯算法 在一些问题求解进程中,有时发现所选用的试探性操作不是最佳选择,需退回一步, 另选一种操作进行试探,这就是回溯算法。 例[6...
回溯法_图文.ppt
回溯法 - 第5章 回溯法 1 ? ? ? ? ? 学习要点 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 (1)递归回溯最优子结构性质 (2)迭代回溯贪心...
算法设计与分析-回溯_图文.ppt
算法设计与分析-回溯 - 第5章 回溯法 1 ? ? ? ? ? 学习要点 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 (1)递归回溯 (2)迭代回溯 ? ...
更多相关标签: