0-1背包问题python

Question

0-1背包问题

题目描述
给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，背包的容量为C。如何选择装入背包的物品，可以使得装入背包中物品的总价值最大？
输入
每组输入包括三行，
第一行包括物品个数n，以及背包容量C。
第二、三行包括两个一维数组，分别为每一种物品的价值和重量。
输出
输出包括两行，第一行为背包的最大总价值，第二行为所选取的物品。
例如：最大总价值=15，物品选取策略为11001。数据保证答案唯一。
样例输入 Copy
5 10
6 3 5 4 6
2 2 6 5 4
样例输出 Copy
15
11001

def knapsack_max_value_and_strategy(v, w, n, c):
    m = [[0] * (c + 1) for _ in range(n + 1)]
    selected_items = [[0] * (c + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for j in range(c + 1):
            if j < w[i]:
                m[i][j] = m[i + 1][j]
                selected_items[i][j] = 0
            else:
                if m[i + 1][j] > m[i + 1][j - w[i]] + v[i]:
                    m[i][j] = m[i + 1][j]
                    selected_items[i][j] = 0
                else:
                    m[i][j] = m[i + 1][j - w[i]] + v[i]
                    selected_items[i][j] = 1

    max_value = m[0][c]
    strategy = ""
    j = c
    for i in range(n):
        strategy += str(selected_items[i][j])
        j -= w[i] * selected_items[i][j]

    return max_value, strategy

while True:
    try:
        n, c = map(int, input().split())
        v = list(map(int, input().split()))
        w = list(map(int, input().split()))
        max_value, strategy = knapsack_max_value_and_strategy(v, w, n, c)
        print(max_value)
        print(strategy)
    except EOFError:
        break

为什么我在oj上运行只有百分之67正确？应该如何修改？

Answer 1

使用动态规划方法求解0-1背包问题。

以上回复有部分引自免费微信小程序：皆我百晓生。 如问题尚未解决，还请稍待，如有疑问请回复进一步沟通。