01背包回溯算法详解 考虑下述背包问题的实例。有5件物品,背包容量为100?
浏览量:1590
时间:2021-03-10 15:06:49
作者:admin
考虑下述背包问题的实例。有5件物品,背包容量为100?
贪心算法在求解问题时总是做出最佳选择(但结果可能不是最好的)
典型算法:prim算法和Kruskal算法
分治算法的基本思想是将一个N尺度的问题分解成k个较小的子问题,
这些子问题相互独立,性质与原问题的原问题解相同。
典型算法:河内塔,对分搜索
动态规划,通过将原问题分解成相对简单的子问题来解决复杂问题的一种方法
典型算法:背包问题
回溯算法,也称为试算法,是一种系统地搜索问题解的方法
典型算法:八皇后问题
根据单位权值的最大优先级策略目前看来是最好的(结果不一定是最好的)
这里是贪心算法,考虑到0/1背包问题,1,2,3的最大值是430(50,200,180)
考虑到部分包含,1,2,3,4(4,40)的最大值是630(50,200,180)]225/45*40)
2,3,4的最大值确实是605,但不是贪心算法计算出来的
所以答案是C
01背包回溯算法详解 01背包问题的回溯算法 回溯算法解决01背包问题
版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。