背包容量N=20,有6个物品,100N等于多少重量力度分别为5,3,2,10,4,2 价值分别为11,8,15,18,

来源：蜘蛛抓取(WebSpider) 时间：2017-05-11 08:18 标签： 上飞机双肩包重量
以下试题来自：
问答题阅读下列说明，回答问题。
0-1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为vi，重量为wi(vi，和wi为非负数)，背包容量为W(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即，且总重量不超过背包容量，即，其中，Xi∈0，1，xi=0表示第i个物品不放入背包，xi=1表示第i个物品放入背包。
用回溯法求解此0-1背包问题，请填充下面伪代码中(1)～(4)处空缺。
回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根节点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前节点，若扩展该节点己经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的节点。现在假设已经设计了BOUND(v，w，k，w)函数，其中v，w，k和W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个节点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该节点无需再扩展。
下面给出0-1背包问题的回溯算法伪代码。
函数参数说明如下。
W:背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X:问题的最优解。
变量说明如下。
cw：当前的背包重量；cp:当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。
BKNAP (W,n,w,v,fw, fp,X)
1 cw←cp←0
4 while true
5 while k≤n and cw+w[k]≤W do
cp← cp+v[k]
if k＞n then
if fp＜cp then
else Y(k)← 0
while BOUND(cp, cw, k, W) ≤fp do
while k≠0 and Y(k) ≠1 do
if k=0 then return
cw←cw-w[k]
cp ← cp-v[k]
考虑表9.2的实例，假设有3个物品，背包容量为22。图9.1中是根据上述算法构造的搜索树，其中节点的编号表示了搜索树生成的顺序，边上的数字1/0分别表示选择/不选择对应物品。除了根节点之外，每个左孩子节点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子节点旁边的数字表示扩展了该节点后最多可能获得的价值。为获得最优解，应该选择物品 (5) ，获得的价值为 (6) 。
　　表9.2 　　0-1背包问题实例
物品1 物品2 物品3
重量 15 10 10
价值 30 18 17
单位价值 2 1.8 1.7
对于表9.2的实例，若采用穷举法搜索整个解空间，则搜索树的节点数为 (7) ，而用了上述回溯法，搜索树的节点数为 (8) 。 [问题1] (1) k←1 (2) cw←cw+w[k]
(3)k←k-1 (4)k←k+1
[问题2] (5)2和3 (6) 35
为您推荐的考试题库
你可能感兴趣的试题
1A．5B．6C．7D．82A．分支限界法B．贪心算法C．回溯法D．动态规划策略3A．O(n2)B．O(n)C．O(nlgn)D．O(1)4A．3B．4C．5D．65A．有穷性B．可行性C．确定性D．健壮性
热门相关试卷
最新相关试卷【图文】概率论1-4章课后习题讲解_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
概率论1-4章课后习题讲解
上传于|0|0|文档简介
&&概率论1-4章课后习题讲解
大小：2.20MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢【图文】算法分析第五章_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
算法分析第五章
上传于|0|0|暂无简介
大小：677.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢背包问题matlab程序_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
背包问题matlab程序
上传于|0|0|文档简介
&&背包问题matlab程序
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢

我要回帖

更多关于 上飞机双肩包重量 的文章

 

随机推荐