完成贪心解求背包问题 输入格式(参考以下格式,) 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、每个物品的价值P以及重量W。

下面是Python代码实现：

n, M = map(int, input().split(','))  # 读入物品数量和背包容量
P = list(map(int, input().split(':')[1].split(',')))  # 读入每个物品的价值
W = list(map(int, input().split(':')[1].split(',')))  # 读入每个物品的重量

# 计算每个物品的性价比（单位重量的价值）
ratio = [P[i] / W[i] for i in range(n)]
# 按照性价比从大到小排序
sorted_idx = sorted(range(n), key=lambda x: ratio[x], reverse=True)

# 贪心选择物品
total_value = 0
selected = [0] * n
for i in sorted_idx:
    if M >= W[i]:
        selected[i] = 1
        total_value += P[i]
        M -= W[i]
    else:
        selected[i] = M / W[i]
        total_value += P[i] * selected[i]
        break

# 输出选择结果和总价值
print('X', end=' ')
print(', '.join([str(x) for x in selected]), end=' ')
print('∑P', end=' ')
print(total_value)

例如，输入n=3,M=20 P:25,24,15 W:18,15,10，输出为X 1, 0, 1 ∑P 39。这表示选择第1和第3个物品，且第3个物品只选择了一半，总价值为39。