贪心算法 部分背包问题 python

贪心算法是一种在每一步选择中都采取在当前状态下最优的选择，从而导致全局最优的算法思想。在实际应用中，贪心算法通常用来解决一些最优化问题，如霍夫曼编码、Prim和Kruskal最小生成树、Dijkstra最短路径等。

部分背包问题是指有一组物品，每种物品都有自己的重量和价格，在限定的总重量内，选择若干个物品装入背包，使得背包内物品总价值最大。与01背包问题不同的是，在部分背包问题中，可以选择某个物品的一部分装入背包，而不一定是全部选择或全部不选。解决部分背包问题的一种有效算法就是贪心算法。

以下是使用贪心算法解决部分背包问题的Python代码：

def fractional_knapsack(cargo, capacity):
    """Return maximum value of items and their fractional amounts.

    (max_value, [(item, amount), ...]) is returned"""
    pack = []
    # 计算每个物品的单位价值
    for c in cargo:
        pack.append((c, c, c/c))
    # 按照单位价值从大到小排序
    pack.sort(key=lambda x: -x)
    # 依次放入物品，直到背包装满为止
    total_value = 0
    result = []
    for p in pack:
        if capacity >= p:
            result.append((p, p))
            capacity -= p
            total_value += p
        else:
            result.append((capacity, p*capacity))
            total_value += p*capacity
            break
    return (total_value, result)