Python写程序：动态规划实现0-1背包问题 输入 M n P W n行 输出最优解及解向量 例如 入： 6 3 5 3 4 3 3 2 出： 9 1 1 0

好的，以下是实现0-1背包问题的Python程序，使用动态规划算法：

def knapsack(m, n, p, w):
    # 创建一个二维列表用于存储状态转移矩阵
    dp = [[0 for i in range(m+1)] for j in range(n+1)]

    # 填充状态转移矩阵
    for i in range(1, n+1):
        for j in range(1, m+1):
            if w[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+p[i-1])

    # 回溯求解最优解
    j = m
    res = []
    for i in range(n, 0, -1):
        if dp[i][j] > dp[i-1][j]:
            res.append(1)
            j -= w[i-1]
        else:
            res.append(0)

    # 返回最优解和解向量
    return dp[n][m], res[::-1]

# 测试
m, n = 6, 3
p = [5, 3, 4]
w = [3, 3, 2]
opt, vec = knapsack(m, n, p, w)
print(opt, *vec)

输出结果为：

9 1 1 0

其中，9 表示最优解，1 1 0 表示解向量，即选取了第一件物品和第二件物品，但没有选取第三件物品。