贪心算法分东西题目

贪心算法是一种求解最优化问题的一种思路，即通过贪心的选择策略，在每个子问题的解决中选择最优解，从而得到全局最优解。在实际生活中，贪心算法有着广泛的应用，在此我们以一道贪心算法经典题目——分东西为例，从不同角度进行分析和探讨。

1. 问题描述

有N件物品和M个人，要将这N件物品分给这M个人，每个人分得的物品必须连续，即要求这N件物品首尾相连。每个人所分得的物品数量由最少的那个人决定，求能分配的最多的物品数量。

例如：有5件物品（1，2，3，4，5），共3个人（A，B，C）需要分配。每个人所分配的物品必须连续。则分配方案可以是：A获得1-2件物品，B获得3-4件物品，C获得5件物品。最多可以分配5件物品。

2. 暴力枚举法

暴力枚举法是最容易想到的思路，首先枚举第一个人所分得的物品数量i（从1到N），然后按照i将物品分给第一个人。接着向后枚举第二个人所分得的物品数量j（j>=i），将第i+1件物品开始的j-i件物品分给第二个人。

以此类推，直到将第m-1个人的物品分配好。最后，将第m个人分配到剩下的所有物品。

暴力枚举法的时间复杂度为O(N^M)，这种解法虽然简单易懂，但随着M的增加，时间复杂度呈爆炸式增长，无法满足实际问题求解的要求。

3. 贪心算法

在分析贪心算法之前，我们思考一个问题：如何让每个人分配到的物品数量尽量均衡？我们需要找到一个基准，比较每个人分配的物品数量和该基准的大小关系，从而得出分配方案。

在此，我们采用最少分配物品数量的人数作为基准。具体算法如下：

（1）找到剩下的物品中连续的长度最小的一段物品，将这一段物品分配给目前分配物品数量最小的人。

（2）将该步骤得到的最小连续物品长度加入到后面分配中，重复进行第1步，直到所有的物品都被分配完毕。

例如：有5件物品（1，2，3，4，5），共3个人（A，B，C）需要分配。 按照上述贪心算法步骤，可以得出分配方案：A获得1-2件物品，B获得3-4件物品，C获得5件物品。最多可以分配5件物品。

4. 贪心算法的正确性证明

在实际问题求解中，我们不仅需要找到可行的解，而且需要找到最优解。我们来证明一下，上述贪心算法对于此问题求得的解是最优解。

（1）对于所有分配方案，首先我们假设有另外一种方案F可以得到更优的结果。假设F方案将某一件物品数分配给了比贪心算法分配给的人更多的个数。也就是说，对于原先分给A的物品，F算法分给了C；对于原先分给C的物品，F算法分给了A，并且F算法可以使A和C都分得更多的物品。

（2）假设在贪心算法的过程中，当需要“成功”的对物品j进行分配时（即该物品是当前最小连续物品段），还存在另外一种不同于F方案的方案G。在方案G中分配给A的物品比F方案多，分配给C的少。也就是说，由于G方案中对B的分配不变，导致A和C的得到更大或更小的分配数。

（3）如果对于情况（1）和情况（2），仅仅是根据题目所给的条件排序，然后依次分配，都能得到最优解，那么F方案和G方案实际上是相同的。此时与设想矛盾。

（4）如果不同，则F方案中A获得的物品比C获得的要多，G中C获得的物品比A获得的要多。因为在F中，C所得到的分配数一定小于B得到的分配数，所以在G中，A所得到的分配数更小。这句话可以换成：在F中A得到的分配数，此时变成分配数最少的数，所以在G中不可能比他或者与他分配数相同。这是因为，将F方案中C所得到的物品分配给A，在G方案中A所得到的物品会更多，而C所得到的物品会更少，与贪心算法给出的结果矛盾，证毕。

5. 时间复杂度

贪心算法解决此问题的时间复杂度为O(N)，相比于暴力枚举法有着明显的优势。在实际应用中，贪心算法的时间效率高，且实现简单，是一种理想的求解思路。

6.