0-1背包问题（python）

Question

0-1背包问题（python）
题目描述
XP每天都会思考一个问题，今天午餐去哪里吃？这是一个很重要的问题，这会影响到他下午的体力值。他的午餐预算是M元，现在有N种菜品，每一种菜品的价格和能够提供的体力值已知（每种菜品只能选择一次），请问如何选择菜品能够让XP下午的体力值最大呢？
输入
多组输入
第一行：M元和菜品数量N。
接下来N行，每一行两个整数，分别表示每一种菜品的价格(vi)和能够获得的体力值(wi)。
（0<N<=20,0<=M<=1000）(0<=vi<=50，0<=wi<=100)
输出
最大体力值。
样例输入 Copy
10 5
1 5
2 4
3 3
4 2
5 1
样例输出 Copy
14
我的代码为什么在oj上提交是百分之50正确，百分之50错误？

while True:
    try:
        c,n= list(map(int, input().split()))
        v=[]
        w=[]
        for i in range(n):
            thing=list(map(int,input().split()))
            v.append(thing[0])
            w.append(thing[1])
        dp = [[0 for i in range(c + 1)] for i in range(n + 1)]
        w.insert(0, 0)
        v.insert(0, 0)
        for i in range(1, n + 1):
            for j in range(1, c + 1):
                if w[i] <= j:
                    if dp[i - 1][j] < dp[i - 1][j - w[i]] + v[i]:
                        dp[i][j] = dp[i - 1][j - w[i]] + v[i]
                    else:
                        dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j]
        print(dp[n][c])
    except EOFError:
        break

Answer 1

引自免费微信小程序：皆我百晓生

根据您提供的代码和问题描述，看起来您正在尝试解决0-1背包问题，这是一个典型的动态规划问题。您的代码实现了一个基本的动态规划解法，但存在一些小问题导致部分测试用例失败。让我们逐步分析并修复这些问题。

首先，我将指出代码中的几个问题，并提供相应的修改建议：

1. 输入格式的问题：当处理多组输入时，您的代码可能无法正确处理。您应该为每组数据添加一个循环，确保程序可以正确读取并处理所有数据。
2. 初始化dp数组：您当前的初始化方式可能会导致一些边界条件不正确。我们应该从第0个元素开始初始化dp数组，使其包含0价值的情况。
3. 更新dp数组时的条件语句：在更新dp[i][j]时，您没有考虑到当w[i] > j的情况，这时不应该选择当前物品，应保持dp值不变。我们可以通过修改条件语句来修复这个问题。

下面是修改后的代码：

def knapsack(m, weights, values, n):
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    # 填充dp表
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if weights[i - 1] <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[n][m]


# 处理多组数据
while True:
    try:
        m, n = map(int, input().split())
        weights = []
        values = []
        for _ in range(n):
            weight, value = map(int, input().split())
            weights.append(weight)
            values.append(value)

        result = knapsack(m, weights, values, n)
        print(result)
    except EOFError:
        break

这个版本的代码应该能正确处理多组输入，并且解决了之前存在的问题。您可以将此代码粘贴到您的IDE或在线编译器中运行，看看是否能得到正确的结果。如果有其他疑问或遇到问题，随时向我提问。