0-1背包问题（分支限界法）报告.doc_分支限界法求01背包问题c语言 - CSDN文库

算法设计与分析实验报告

需积分: 36 152 浏览量更新于2023-03-03 评论 5 收藏 94KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

实验十六：0-1 背包问题（分支限界法）报告

2017061111 李静娴

1．问题描述

给定  种物品和一背包。物品  的重量是 ，其价值为 ，背包的容量为 。问应如何选

择装入背包的物品，使得装入背包中物品的总价值最大

2．实验目的

（1）熟悉分支限界法，并学以致用

（2）熟练掌握 0-1 背包问题算法

3．实验原理

首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在

优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值

的物品装满剩余容量的价值和。

算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，

则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，

仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时

为问题的最优值。

算法的时间复杂度：‰。

4．实验设计

（）

输入数据格式：宏定义集装箱个数 ，背包容量以及物品质量和价值由用户自定义

生成方式：用户输入

数据规模：宏定义设定。

（）

该程序先是设定好物品个数，然后由用户设定背包容量以及物品的质量和价值。再调

用 Knapsack(p, w, c, n)函数输出背包能装下的最大价值。bestx[i]输出最优解。

（）

程序运行的结果有四部分，先是输出背包容量，再输出物品重量和价值，然后输出背

包能装的最大价值，最后输出最优解。

5．实验结果与分析

剩余11页未读，继续阅读

评论0

qq_42236488

粉丝: 4
资源: 17

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈