假设你是个贪婪的小偷,背着可装35磅(1磅≈0.45千克)重东西的背包,在商场伺机盗窃各种可装入背包的商品。

你力图往背包中装入价值最高的商品,你会使用哪种算法呢?

同样,你采取贪婪策略,这非常简单。

  1. 盗窃可装入背包的最贵商品。
  2. 再盗窃还可装入背包的最贵商品,以此类推。

只是这次这种贪婪策略不好使了!例如,你可盗窃的商品有下面三种。

你的背包可装35磅的东西。音响最贵,你把它给偷了,但背包没有空间装其他东西了。

你偷到了价值3000美元的东西。且慢!如果不是偷音响,而是偷笔记本电脑和吉他,总价将为3500美元!

从这个示例你得到了如下启示:在有些情况下,完美是优秀的敌人。有时候,你只需找到一个能够大致解决问题的算法,此时贪婪算法正好可派上用场,因为它们实现起来很容易,得到的结果又与正确结果相当接近。

results matching ""

    No results matching ""