用python完成贪心解求背包问题

好的，背包问题是经典的贪心算法问题之一。下面是用 Python 实现贪心算法求解背包问题的代码：

n, M = map(int, input().split())  # 输入n和M
P = list(map(int, input().split()))  # 输入P数组
W = list(map(int, input().split()))  # 输入W数组

# 计算每个物品的性价比
value = []
for i in range(n):
    value.append(P[i] / W[i])

# 贪心算法求解背包问题
sum_p = 0
x = [0] * n
while M > 0:
    max_value = 0
    max_index = -1
    for i in range(n):
        if x[i] == 0 and value[i] > max_value:
            max_value = value[i]
            max_index = i
    if max_index == -1:
        break
    if M >= W[max_index]:
        x[max_index] = 1
        M -= W[max_index]
        sum_p += P[max_index]
    else:
        x[max_index] = M / W[max_index]
        sum_p += x[max_index] * P[max_index]
        M = 0

# 输出结果
print("X", end=" ")
for i in range(n):
    print("{:.1f}".format(x[i]), end=" ")
print(" \u2211P", sum_p)

上面的代码实现了输入 n 和 M，以及两个数组 P 和 W，其中 P 表示每个物品的价值，W 表示每个物品的重量。

接下来，我们计算每个物品的性价比 value，并初始化 x 数组为全 0。

然后，我们进入贪心算法的循环，每次循环找到性价比最大的未选择的物品，如果该物品的重量小于等于背包剩余容量 M，则将该物品全部放入背包，并将 x 数组对应位置置为 1，否则按比例将该物品放入背包并更新 x 数组，直到背包装满或所有物品都被选择。

最后，我们输出结果，其中 X 表示每个物品被选择的比例，∑P 表示背包中选择的物品的总价值。

希望这段代码能对您有所帮助！