贪心法求解一般背包的代码

贪心算法通常不是解决背包问题的理想选择，因为背包问题通常属于0-1整数线性规划问题，而贪心策略并不一定能保证得到全局最优解，特别是当物品的价值重量比不同时。不过，对于一些特殊情况下的简单版本，如 knapsack with weights as multiples of a common divisor 或者 fractional knapsack（部分装满），可以设计出基于贪婪的解决方案。

经典的贪婪算法是 `Fractional Knapsack`，其特点是所有物品都有一个固定的价格单位价值（value per unit weight）。在这种情况下，你可以按单位价值从大到小选取物品，直到背包填满或者没有更多的空间。

以下是使用 Python 编写的 Fractional Knapsack 的基本思路：

def fractional_knapsack(weights, values, W):
    # 创建一个二维列表，表示每个单位重量的价值
    value_per_weight = [v/w for w, v in zip(weights, values)]
    
    # 按单位价值降序排序
    sorted_items = list(zip(weights, values, value_per_weight)) 
    sorted_items.sort(key=lambda x: -x[2])
    
    total_value = 0
    i = 0
    
    while total_value < W and i < len(sorted_items):
        if sorted_items[i][0] <= W:
            # 可以完全放入当前物品
            total_value += sorted_items[i][1]
            W -= sorted_items[i][0]
        else:
            # 部分填充，取最大单位价值的部分
            fraction = W / sorted_items[i][0]
            total_value += sorted_items[i][1] * fraction
            break  # 确保剩余空间不会浪费

    return total_value

# 示例
weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
print(fractional_knapsack(weights, values, W))