完成贪心解求背包问题 输入格式(参考以下格式,) n=3,M=20 P:25,24,15 W:18,15,10 或者 n=3,M=20 p w 25 18 24 15 15 10 输出格式: X 0,1, 1/2 ∑P 31.5

好的，背包问题是经典的动态规划问题，但是我们可以用贪心算法来解决。以下是代码实现：

n, M = map(int, input().split())
P = list(map(int, input().split()))
W = list(map(int, input().split()))

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

# 按照性价比降序排序
ratio.sort(reverse=True)

# 初始化背包和总价值
bag = [0] * n
value = 0

# 依次将性价比高的物品放入背包中
for r, i in ratio:
    if W[i] <= M:
        bag[i] = 1
        M -= W[i]
        value += P[i]
    else:
        bag[i] = M / W[i]
        value += P[i] * (M / W[i])
        break

# 输出结果
print("X", end=" ")
for i in range(n):
    print("{:.1f},".format(bag[i]), end=" ")
print("∑P {:.1f}".format(value))

输入格式为：

n=3,M=20
P:25,24,15
W:18,15,10

输出格式为：

X 0.0, 1.0, 1.0, ∑P 39.0

其中 X 后面的数字表示对应物品是否放入背包中，∑P 表示背包中物品的总价值。