贪心算法（简单易懂，考研复试上机知识点）

• Python

贪心算法简介：

 

贪心算法，思路也是非常简单的，每一步总是做出在当前看来最好的选择。

贪心算法的核心就是无后效性，也就是说当前的决策不会影响之后的决策，是独立的。

dp（动态规划）是有后效性的，当前的决策会影响到之后的决策，是有关联的。

 

下面举例对比：

 

01背包问题。

有一个背包，背包容量是M=30。有3个物品，要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

我们制定贪心的策略总共有3种：

1. 每次挑选重量最小的放入背包

2. 每次挑选价值最大的放入背包

3. 每次挑选单位重量价值最大的放入背包

我们试着来证明这三种可行：

第一种：

物品：A B C

重量 10 30 10

价值 20 80 20

每次挑选重量最小，AC放入背包后，B就不能放入背包了，放入AC的价值为40，而选择放入B的价值为80，明显不成立

第二种：和第一种类似

第三种：

物品：A B C

重量 10 30 10

价值 10 30 10

每次挑选单位重量价值最大，ABC的单位重量价值都一样，无法选择，因此也不成立

 

结论：

我们不能使用贪心算法，但是如果物品是可拆分的话，那么我们就可以求最大最小问题，因为当前的选择不会影响到其他物品的选择，是独立的。

所以我们应该使用动态规划，选择每个物品都会影响到其它物品的选择，是有后效性的，不是独立的。

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/f8b3c273fc.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐