趣味算法第二章-例题

14天阅读挑战赛

贪心算法-例题

一：最优装载问题

海盗们截获一艘装满各种各样古董的货船，每一件古董都价值连城，但一旦打碎就会失去其原有的价值。海盗船虽然足够大，但载重量是有限的。海盗船的重量为W，每件古董的重量为Wi，如何才能把尽可能多的古董装上海盗船呢？

（1）问题分析 

问题要求装载的古董尽可能多，在载重量有限的情况下，优先把重量最小的古董装进去，装的古董越多。可以采用重量最小者先装的贪心策略，从局部最优解达到全局最优，从而得到最优装载问题的最优解。

（2）算法设计

1.把n个古董的重量从小到大（非递减）排序

2.根据贪心策略选择装入的古董，直到不能继续装为止，此时达到最优。

（3）完美图解 

每个古董的重量如表2-1所示，海盗船的载重量W为30，在不打碎古董且不超出载重量的情况下，怎样才能装入最多的古董呢？

1.贪心策略是每次选择重量最小的古董装入海盗船，因此对表2-1按照古董重量进行非递减排序，排序结果如表2-2所示。

 2.按照贪心策略，每次选择重量最小的古董装入海盗船（tmp代表已装入的古董重量，ans代表已装入的古董数量）。

 （4）算法详解

（5）算法分析及优化拓展 

1. 算法复杂度分析

   （1）时间复杂度：用于排序古董重量的sort函数的平均时间复杂度为O(nlogn)，贪心策略求解的时间复杂度为O(n)，O(n)比O(nlogn)小，忽略小项，因此总的时间复杂度为O(nlogn)。

   （2）空间复杂度：辅助空间为tmp、ans等变量，它们都是常数阶的，因此空间复杂度为O(1)

2.优化拓展

 二：阿里巴巴与四十大盗——背包问题

 （1）问题分析

本题为可分割背包问题，可以尝试贪心策略。

1.每次选择价值最大的物品装入背包

2.每次选择重量最小的物品装入背包

3.每次选单位重量价值最大的物品装入背包

采用第三种贪心策略——每次从剩下的物品中选单位重量价值最大的物品。

（2）算法设计

 （3）完美图解

 1.贪心策略是每次选单位重量价值（价值/重量）大的物品，因此可以按单位重量价值对物品进行降序排序，排序后的物品清单如表2-4 所示。

 2.按照贪心策略，每次选择单位重量价值大的物品装入背包

 3.构造最优解

 （4）算法详解

 （5）算法分析及优化拓展

1 . 算法复杂度分析

    （1）时间复杂度：时间主要耗费在对物品按单位重量价值进行排序上，一般采用快速排序法，时间复杂度为O(nlogn)

    （2）算法优化拓展