贪心算法概念理解精讲

   所谓贪心算法，是指从问题的初始状态出发，通过若干次的贪心选择而得到的最优值（或较优值）的一种求解问题策略，即贪心策略。

  话不多说，从下面的引例中你会很容易明白贪心策略：
   在N行M列的正整数矩阵中，要求从每一行中选出一个数，使得选出数的总和最大。
   分析：思路很简单，选择N次，每次从当前行选出最大值，最后相加即可。其实这就是一种贪心策略。要求使总和最大，那么我们把这个问题分解成若干个子问题，即求每一个子问题的最优解，汇总后得到大问题的最优解。
   这个问题很简答易懂，但是不要认为贪心就是这样简单的问题，笔者目的在于快速引导大家认识贪心的本质，即分为四个步骤：建立数学模型（使问题具象化，有利于分析问题）；分解为若干子问题；对子问题求解，的到子问题的局部最优解；把子问题的局部最优解合成原来问题的一个解。

   读者可以自行分析以下几个问题加深对贪心策略的理解：
   最优装载问题：给 N 个物体，第 i 个物体的重量为 Wi ，尽量选择多的物体，使得总重量不超过C。
   部分背包问题：有 N 个物体，第 i 个物体的重量为 Wi ，价值为 Vi ，在总重量不超过 C 的情况下让总价值尽量高，每一个物体可以只取走一部分，价值和重量按比例计算。
   乘船问题：有 N 个人，第 i 个人的重量为Wi ，每艘船的载重量均为C最多可乘两个人。求最少得用多少条船才能装下所有的人。