循序渐进，搞懂什么是贪心算法
贪心算法简介
贪心算法（greedy algorithm）又称贪婪算法，指在求解最优化问题时，每一步都选择在当前状态下最好或最优的策略，从而逐步推导出最优解的算法。
贪心算法不从整体最优上加以考虑，它所做出的选择只是局部最优选择。这种策略的显著特点是“目光短浅”，只看重眼前最好的选择，而不考虑更长远的结果。因此，贪心算法不是对所有问题都能得到整体最优的解。对于一些问题，它只能得到局部最优解，局部最优解并不一定是整体最优解，不过，通常是近似最优解。
贪心算法的典型应用包含：部分背包问题、霍夫曼编码（huffman coding）、最小生成树（普利姆算法，prim’s algorithm）、单源最短路径问题（迪杰斯特拉算法，Dijkstra’s algorithm）等。
贪心算法的关键是构造适合的贪心策略。贪心算法执行时根据贪心策略做出最优选择，不考虑各种可能的情况，省去了穷尽所有可能的选项而耗费的时间。因此贪心算法的运行效率高，运行时间较短。
贪心算法的一般求解步骤
贪心算法没有固定的解题套路，不过对一般情况，使用贪心算法，需要先对问题进行分析，可以参考如下的一般求解步骤。
问题定义：明确问题的输入、输出和目标。
状态定义：将问题分解为多个阶段，每个阶段都有一个状态。状态通常由问题的某些属性表示。
确定贪心策略：在每个阶段，根据当前状态选择最优决策，以期望达到全局最优解。这个最优决策通常是最优子结构的一部分，问题的最优解可以通过其子问题的最优解来获得，则问题具有最优子结构，这意味着每个阶段的最优决策都是全局最优解的一部分。
代码实现：根据上述步骤设计贪心算法，编写代码。通常，贪心算法包括一个循环，每次循环中都选择当前最优决策，并更新状态。
算法分析：分析贪心算法的正确性和可行性。
贪心算法实现举例
贪心算法最简单易懂的应用是部分背包问题，下面直接看一个例子。
假设有一个能装下50磅重的背包，有5件不同的物品，它们的重量分别为[5, 10, 30, 20, 5]，价值分别为[80, 200, 300, 150, 30]，这5件物品都可以按每磅获取其中的一部分。为了使背包装下的物品价值最高，应该在背包中装哪些物品？最高价值是多少？
def part_backpack(weight_bp, weights, values):
"""部分背包问题"""
# 计算单价并按从高到低排序
unit_value = []
for i in range(len(weights)):
unit_value.append((f'w{
i+