python贪心算法0-1背包问题_【算法】贪心算法(0-1背包问题)

0-1背包问题是一个经典的优化问题，在很多领域都有应用。贪心算法是解决0-1背包问题的一种有效方法。

问题描述：

有一个容量为C的背包，和n个物品，每个物品有重量w和价值v。要求在不超过背包容量的情况下，选择若干个物品放入背包，使得背包中的价值最大。

贪心算法思路：

1. 按单位重量价值从大到小排序。

2. 依次选择单位重量价值最大的物品放入背包，直到背包装满或者物品用完。

代码实现：

def knapsack(C, w, v):
    n = len(w)
    # 按照单位重量价值从大到小排序
    val_per_weight = [(v[i] / w[i], i) for i in range(n)]
    val_per_weight.sort(reverse=True)

    # 初始化背包
    total_value = 0
    cur_weight = 0
    knapsack = [0] * n

    # 依次选择单位重量价值最大的物品放入背包
    for val, i in val_per_weight:
        if cur_weight + w[i] <= C:
            knapsack[i] = 1
            cur_weight += w[i]
            total_value += v[i]
        else:
            break

    return total_value, knapsack

参考资料：

[1] https://www.cnblogs.com/liuzhen1995/p/8978740.html