没有合适的资源?快使用搜索试试~ 我知道了~
首页实验三:贪心算法,回溯法与分支限界法.docx
本实验报告问题描述: 0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大? 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。在选择物品i装入背包时,可以选择i的一部分,而不一定要全部装入。应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大? Prim算法:一个无向连通图的生成树是一个极小连通子图,它包括图中全部的结点,并且尽可能少的边。遍历一个连通图得到图的一颗生成树。 Kruskal算法:一个无向连通图的生成树是一个极小连
资源详情
资源评论
资源推荐
算法设计与分析实验报告
实验三:贪心算法,回溯法与分支限界法
姓 名:
学 号:
班 级:
专 业:计算机科学与技术
院 系: 信息工程学院
一、问题描述
0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是
wi,其价值为 vi 。应该如何选择装入背包的物品,使得装入背包中的物品的总
价值最大?
背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,
其价值为 vi 。在选择物品 i 装入背包时,可以选择 i 的一部分,而不一定要全
部装入。应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?
Prim 算法:一个无向连通图的生成树是一个极小连通子图,它包括图中全
部的结点,并且尽可能少的边。遍历一个连通图得到图的一颗生成树。
Kruskal 算法:一个无向连通图的生成树是一个极小连通子图,它包括图
中全部的结点,并且尽可能少的边。遍历一个连通图得到图的一颗生成树。
装载问题回溯法:有一批共 n 个集装箱要装上 2 艘载重量分别为 c1 和 c2
的轮船,其中集装箱 i 的重量是 wi,且不能超,即 Σwi<=c1+c2。
装载问题分支限界法:有一批共 n 个集装箱要装上 2 艘载重量分别为 c1 和
c2 的轮船,其中集装箱 i 的重量是 wi,且不能超,即 Σwi<=c1+c2。
二、问题分析
0-1 背包问题:顺序选取物品装入背包,假设已选取了前 i 件物品之后背包
还没装满,则继续选取第 i+1 件物品,若选该件物品的重量太大不能装入,则
放弃而继续选取下一件,直至背包装满为止。但是如果在剩余物品中找不到合
适的物品以填满背包,则说明“刚刚”装入背包的那件物品“不合适”,应该将它取
出,再继续从它之后的物品中选取,如此重复,直至求得满足要求的解,或者
无解为止。这里我使用了二维数组每一行都有两个元素分别表示一个物品的重
量和价值。
背包问题:这里给出了一个物品的总价值和其重量,我使用了二维数组每
一行两个元素分别表示一个物体的总价值和重量。首先需要求出每个物品的单
价,然后对其进行从大到小排序,先取单价最大的,依次放入,每次放入一件
物品就让背包总重量 v 减去该物品的总重量,并让背包所装物品总价值 sum 加
上所装物品总价值。当最终所剩重量小于 0 时(即最后一件物品装不完),则
取出最后装的一件物品,即让所剩重量 v 加上最后一件物品的重量,然后总价
值 sum 减去最后一件物品总重量。然后看看最后一件物品能装入多少,让总价
值加上最后装的物品的价值,输出即可。
Prim 算法:
设 G=(V,E)G=(V,E)是带权的连通图,F=(U,S)F=(U,S)是图 G 的子图,
它是正在构造中的生成树。普里姆算法从 U={v0}U={v0},S=∅S=∅开始
构造最小代价生成树,其中 v0,v0∈Vv0,v0∈V 是任意选定的结点。普里姆算
法的具体选边准则是:寻找一条边(u,v)(u,v),它是所有一个端点 u 在构造的
生成树上(u∈U)(u∈U),而另一个端点 v 不在该树上(v∈V−U)(v∈V−U)的这
些边中代价最小的边。算法按照上述选边准则,选取 n-1 条满足条件的最小边
加到生成树上,最终 U=VU=V。这时,T=(V,S)T=(V,S)是图 G 的一颗最小
代价生成树。
Kruskal 算法:
先构造一个只含 n 个顶点、而边集为空的子图,把子图中各个顶点看成各
棵树上的根结点,之后,从网的边集 E 中选取一条权值最小的边,若该条边的
两个顶点分属不同的树,则将其加入子图,即把两棵树合成一棵树,反之,若
该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的
边再试之。依次类推,直到森林中只有一棵树,也即子图中含有 n-1 条边为止。
装载问题回溯法:在给定的装载问题有解的情况下,最优装载方案: 首先
将第一艘轮船尽可能的装满;然后将剩余的集装箱装上第二艘轮船。将第一艘
轮船尽可能的装满等价于选取全体集装箱的一个子集,使该子集中集装箱重量
之和最接近 c1。先考虑装载一艘轮船的情况,依次讨论每个集装箱的装载情况,
共分为两种,要么装(1),要么不装(0),因此很明显其解空间树可以用子集树
来表示。
装载问题分支限界法:在算法的循环体中,首先检测当前扩展结点的左儿
子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子
结点加入到活结点队列中(右儿子结点一定是可行结点)。2 个儿子结点都产生
后,当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点,
由于队列中每一层结点之后都有一个尾部标记-1,故在取队首元素时,活结点
队列一定不空。当取出的元素是-1 时,再判断当前队列是否为空。如果队列非
剩余17页未读,继续阅读
qq_44080211
- 粉丝: 0
- 资源: 11
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0