华体会- 华体会体育- 体育官网01背包问题的贪心算法

2025-04-18 10:47:27

　　华体会,华体会体育,华体会体育官网,华体会靠谱吗,华体会APP(访问: hash.cyou 领取999USDT）

　　第１３卷第６ 期Ｖ ０ １． １３ Ｎ ｏ ． ６鄂州大学学报Ｊｏ ｕ ｒｎ ａ ｌ ｏ ｆ Ｅ ｚ ｈ ｏ ｕＵ ｎ ｉｖ ｅ ｒ ｓｉｔｙ２０ ０ ６ 年１１月Ｎ Ｏ Ｖ ． ２ ０ ０ ６０ １１背包问题的贪心算法黄宇林（ 鄂州大学基础科学系， 湖北鄂州４ ３６ ０ ０ ０ ）摘要： ０ ／１背包问题属于动态规划问题， 部分背包问题属于贪心算法的范畴， 通过比较两种算法的联系和区别， 来寻求０ ／１背包问题的贪心算法的条件， 用贪心算法来解决部分０ ／１背包问题的求解。关键词： 动态规划； 贪心算法； ０ ／１背包问题中图分类号： ０ ２２３文献标识码： Ａ文章编号： １０ ０ ８ —９ ０ ０ ４ （ ２０ ０ ６）０ ６—０ ０ ３８ —０ ３１问题的提出背包问题分为部分背包问题和０ ／１背包问题两种。 部分背包问题在选择物品时， 可以将物品分割为部分装入背包， 即０ ≤麓≤１ｒ” ， 很显然属于贪心算法的范畴， 用贪...

　　第１３卷第６ 期Ｖ ０ １． １３ Ｎ ｏ ． ６鄂州大学学报Ｊｏ ｕ ｒｎ ａ ｌ ｏ ｆ Ｅ ｚ ｈ ｏ ｕＵ ｎ ｉｖ ｅ ｒ ｓｉｔｙ２０ ０ ６ 年１１月Ｎ Ｏ Ｖ ． ２ ０ ０ ６０ １１背包问题的贪心算法黄宇林（ 鄂州大学基础科学系， 湖北鄂州４ ３６ ０ ０ ０ ）摘要： ０ ／１背包问题属于动态规划问题， 部分背包问题属于贪心算法的范畴， 通过比较两种算法的联系和区别， 来寻求０ ／１背包问题的贪心算法的条件， 用贪心算法来解决部分０ ／１背包问题的求解。关键词： 动态规划； 贪心算法； ０ ／１背包问题中图分类号： ０ ２２３文献标识码： Ａ文章编号： １０ ０ ８ ９ ０ ０ ４ （ ２０ ０ ６）０ ６０ ０ ３８ ０ ３１问题的提出背包问题分为部分背包问题和０ ／１背包问题两种。 部分背包问题在选择物品时， 可以将物品分割为部分装入背包， 即０ 麓１ｒ” ， 很显然属于贪心算法的范畴， 用贪心算法能较好地解决其求解。 下面来讨论０／１背包问题。ｏ ， １背包问题： 设有ｎ 种东西可以装入背包。 埘，是第ｉ种东西的重量， 秽， 是它的价值， 为是装入背包中的第ｆ 种东西的个数， 设ｂ （ ｂ ＞ ０ ）是背包总重量的最大值。 则背包问题可表示为：Ｚ ＝ ， 臌 ， ， ｘ，Ｖ Ｊ０产１（ 菇， 为非负整数）ｎＥ Ｗ ， ｘ ， ｓｂＪ二ｌＷ Ｊ０设Ｆ Ｋ （ ｙ ）是背包中只装第ｋ 种东西。 总重量限制为ｙ 的情况下所具有的最大值， 即Ｉ、 广Ｒ （ ｙ）＝ 础乞％（ Ｄ ｜ｊ｝兰ｎ：１＝ １Ｉ． ，ｗ ｉｘｉ垒， ，ｉ＝ ｌ（ Ｄ ｙ ６）不难看出背包问题满足优化原则。 我们可以使用动态规划的方法， 所得的递推等式和边界条件是：最（ ｙ）＝ ｍ ａｘ｛ Ｆ ｋ－ ｌ（ ｙ）， Ｅ （ Ｍ ＾）切＾）Ｆ ｏ （ ｙ ）＝ Ｏ ， 对于一切Ｙ ， Ｄ 兰）， ６最（ ０）＝ ０， 对于一切ｋ ，Ｄ 兰｜ｊ｝ｎ为了求解的方便， 定义Ｙ 为负数时， Ｆ ｋ （ ｙ ）一ｏ ｏ ［ ２］用动态规划求解是理所当然的。 同时我们知道在一般情况下， 贪心算法不适于解０ ／１背包问题，但在特殊的情况下。 用贪心算法也能解决部分０ ／１背包问题。 而且求解非常简洁。２动态规划与贪心算法的区别与联系２． １联系都是通过局部最优解得到整体最优解。２． ２区别贪心算法是指从问题的初始状态出发， 通过若干次的贪心选择而得出最优值（ 或较优解）的一种解题方法， 贪心策略总是做出在当前看来最优的选择， 并不是从总体上加以考虑， 它所做的选择只是在某种意义上的局部最优解。它采用自顶向下。 以迭代的方法做出相继的贪心选择。 每做一次贪心选择就将所求问题简化为一个规模更小的子问题， 通过每一步贪心选择， 最终可得到问题的一个最优解［ ３】 。动态规划是在每一步判断的时候只须考虑与它有关的前一步的情况而与以前的各步的判断没有关系。 解决这类问题的方法是： 把问题化成多步判断的问题， 在每步作出判断时， 只考虑由初始决策所确定的当前状态。它采用自底向上的顺序， 找到边界条件， 将整个问题的最优解与问题的局部最优解用递推的等式联系起来， 把边界条件代入递推等式逐步求得最优解。３ ０ ／１背包问题的贪心算法背包问题有多种贪婪策略， 每种策略都需经收稿日期： ２０ ０ ６ － ０ ２１４作者简介： 黄宇林（ １９ ６５一）， 男。 湖北鄂州人， 鄂州大学基础科学系讲师， 研究方向： 数学教育。万方数据

【返回列表】