贪心算法是一种在每一步选择中都做出在当前看来最佳的选择，从而希望导致结果是最优的算法。 举个例子，假设我们有一个可以装下重量不超过 W 的背包，并有 n 件物品，第 i 件物品的重量为 w[i]，价值为 v[i]。我们希望从中选出若干件物品，装到背包中，使得装入背包中物品的总价值最大。 这个问题就可以使用贪心算法来解决。考虑按照价值与重量的比值来排…