用贪心算法解决0/1背包问题和解决背包问题的区别
答案:2 悬赏:0 手机版
解决时间 2021-07-26 07:29
- 提问者网友：爱了却不能说
- 2021-07-25 10:28
用贪心算法解决0/1背包问题和解决背包问题的区别 （简答）
最佳答案
- 五星知识达人网友：酒者煙囻
- 2021-07-25 11:57
我先讲下0/1背包和完全背包的区别
0/1背包：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。特点是每件物品都只有一件
完全背包：概念和上面一样。但特点是每件物品都有无限个。
贪心法：每一步选择都选择最优，从而希望导致全局最优。
-------------------------------------------------------------------------------
用贪心法是不能解决0/1背包和完全背包问题的。要用动态规划。（每一步的最优选择不能保证结果最优，因为背包是有容量的。）
---------------------------------------------------------------------------------
看来楼主对贪心法和动态规划还是不是很清楚。
http://www.china001.com/show_hdr.php?xname=PPDDMV0&dname=J2PCV41&xpos=46
全部回答
- 1楼网友：鸠书
- 2021-07-25 12:19
除了部分背包
其它的都不能用贪心做出来
要用动态规划
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯