0/1背包问题的贪心算法.pdf
文本预览下载声明
第 13卷 第 6期 鄂 州 大 学 学 报 2006年 l1月
Vo1.13No.6 JournalofEzhou University NOV.2006
0/1背包问题的贪心算法
黄宇林
(鄂州大学 基础科学系,湖北 鄂州436000)
摘 要:0/1背包问题属于动态规划问题,部分背包问题属于贪心算法的范畴,通过比较两种算法的联
系和区别,来寻求0/1背包问题的贪心算法的条件,用贪心算法来解决部分0/1背包问题的求解。
关键词:动态规划 ;贪心算法 ;0/1背包问题
中图分类号:0223 文献标识码 :A 文章编号 :1008—9004(2006)06—0038—03
1 问题的提出 用动态规划求解是理所当然 的.同时我们知
背包问题分为部分背包问题和0/1背包问题两 道在一般情况下.贪心算法不适于解0/1背包问题,
种。部分背包问题在选择物品时,可以将物品分割 但在特殊的情况下.用贪心算法也能解决部分0/1
为部分装人背包,flO0~x≤1t”,很显然属于贪心算 背包问题,而且求解非常简洁。
法的范畴,用贪心算法能较好地解决其求解。下面 2 动态规划与贪心算法的区别与联系
来讨论0/1背包问题 。 2.1联系
0/1背包问题 :设有n种东西可以装人背包, 都是通过局部最优解得到整体最优解。
是第 种东西的重量,vi是它的价值 ,xj是装人背包 2.2 区别
中的第 种东西的个数 ,设b(b0)是背包总重量的 贪心算法是指从问题的初始状态出发.通过若
最大值 .则背包问题可表示为: 干次的贪心选择而得出最优值(或较优解)的一种
解题方法,贪心策略总是做 出在当前看来最优的选
Z=max∑VJ V7≥0 择,并不是从总体上加 以考虑,它所做的选择只是
, 为非负整数) 在某种意义上的局部最优解 。
∑wJ ≤b ⅥJ,≥0 它采用 自顶向下.以迭代的方法做出相继的贪
心选择,每做一次贪心选择就将所求 问题简化为
设FK(y)是背包 中只装第k种东西,总重量限 个规模更小的子问题 .通过每一步贪心选择,最
制为 的情况下所具有的最大值,即
终可得到问题的一个最优解3]『。
k
1 动态规划是在每一步判断的时候 只须考虑与
(y)=mxa vjxj (D )
i=l 它有关的前一步 的情况而与以前的各步的判断没
k
有关系.解决这类问题的方法是:把 问题化成多步
∑ ,, (D),6)
= J 判断的问题,在每步作出判断时,只考虑 由初始决
不难看出背包问题满足优化原则 .我们可 以 策所确定的当前状态 。
使用动态规划的方法 ,所得 的递推等式和边界条
显示全部