首页 > 代码库 > 0-1 背包问题、背包问题、最优装载问题、哈夫曼编码,这几个问题的思想是什么?
0-1 背包问题、背包问题、最优装载问题、哈夫曼编码,这几个问题的思想是什么?
0-1背包问题:
给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。
背包问题:
与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1≤i≤n。
解决方法:求每个物品的价值重量比,即价值/重量。然后添加价值重量比最大的物品,添加结束如果未达到重量上限,再添加价值重量比次大的。
最优装载问题:
有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。
解决方法:每次装重量最轻者。
哈夫曼编码:
给出现频率高的字符较短的编码,出现频率较低的字符以较长的编码。对每一个字符规定一个0,1串作为其代码,并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。
以上四个问题都可以用贪心法的思想求解,从许多可以用贪心法求解的问题中可以看到它们一般具有两个重要性质:贪心选择性质、最优子结构性质
其中,所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通过以自顶向下的方式进行。
当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质
0-1 背包问题、背包问题、最优装载问题、哈夫曼编码,这几个问题的思想是什么?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。