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

回溯算法_01背包问题


背包回溯算法 背包回溯算法 班级: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); }


相关文章:
01背包问题回溯算法
01背包问题回溯算法 - 假设有 7 个物品,它们的重量和价值如下表所示。若这些物品均不能 被分割,且背包容量 M=150,使用回溯方法求解此背包问题。请写 出状态...
回溯法求01背包问题
回溯法01背包问题 - 实验题目 给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值 为 vi,0/1 背包问题是如何选择装入背包的物品(物品不可...
蛮力法、动态规划法、回溯法和分支限界法求解01背...
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题 - 一、实验内容: 分别用蛮力法、动态规划法、回溯法和分支限界法求解 0/1 背包问题。 注: 0/1 背包...
01背包问题不同算法设计、分析与对比
01背包问题不同算法设计、分析与对比 - 实践动态规划、贪心、回溯以及分支限界算法程序设计
回溯算法解决0-1背包问题(DOC)
回溯算法解决0-1背包问题(DOC) - 《算法分析与设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: 信息工程学院 实验项目名称...
回溯法解0-1背包问题实验报告
实验4 一 、实验要求 回溯法0-1 背包问题 1.要求用回溯法求解 0-1 ...文档贡献者 我是伊大头 贡献于2018-07-01 1 /2 相关文档推荐 ...
算法实验报告01背包问题
算法实验报告01背包问题 - hebut的,你懂得。动态规划、贪心算法回溯法三种方法的实现。仅供参考,有能力还是鼓励自己做
回溯法实验(0-1背包问题)
回溯法实验(0-1背包问题) - 算法分析与设计实验报告 第五 次附加实验 姓名 时间 实验名称 12.26 上午 学号 地点 班级 工训楼 309 回溯法实验(0-1 背包...
回溯法求0-1背包问题
回溯法0-1背包问题 - 《算法设计与分析》实验报告 学日号: 期: 姓得名: 分: 一、实验内容: 用回溯法求解 0/1 背包问题 注:给定 n 种物品和一个容量...
算法分析与程序设计动态规划及回溯法解01背包问题...
算法分析与程序设计动态规划及回溯法01背包问题 - 动态规划法、回溯法0-1 背包问题 2012 级 计科 庞佳奇 一、 1. 问题描述与分析 动态规划算法通常用于...
更多相关标签: