猫史档案馆

大家好我是奶思呀-。-

今天呢和大家分享一个经典的算法

贪心算法

 

这玩意有什么用呢？

先来个游戏 简单的模拟一哈真实场景啊

 

贪心算法每一步必须满足一下条件：

1、可行的：即它必须满足问题的约束。

2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。

3、不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。

 

[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。 

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 

物品 A B C D E F G 

重量 35 30 60 50 40 10 25 

价值 10 40 30 50 35 40 30 

记得当时学算法的时候，就是这个例子，可以说很经典。 

分析： 

目标函数： ∑pi最大 

约束条件是装入的物品总重量不超过背包容量，即∑wi<=M( M=150) 

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ 

（2）每次挑选所占重量最小的物品装入是否能得到最优解？ 

（3）每次选取单位重量价值最大的物品，成为解本题的策略? 

--------------------- 

（本段复制与 者：半笙彷徨 

来源：CSDN 

原文：https://blog.csdn.net/wang704987562/article/details/70991590 

版权声明：本文为博主原创文章，转载请附上博文链接！）

最后附上游戏