15588686105 发表于 2023-8-9 17:23:54

python 的01背包结果有问题

#n种物品，每种物品只有一件   物品只有拿不拿两种状态
#dp:在物品中任拿，所能将容量位j的背包价值最大化
#dp=max(dp]+val,dp)
def maxvalue(n,m,weight,value):

    # 创建二维dp数组
    dp=[for j in range(n)]

    # 初始化
    for j in range(m):
      if j < weight:
            continue
      dp = value

    #   遍历
    for i in range(1,n):
      for j in range(m):

            # dp公式
            if(j < weight):
                dp = dp
            else:
                dp = max(dp] + value,dp)
    # return dp;
    print(dp)

n=input("输入物品个数：")   # input返回str型
m=input("输入背包容量 ")
weight= * int(n)
value= * int(n)
for i in range(int(n)):
    weight = int(input("{}{}{}".format("输入物品" , i ,"的重量：")))
for i in range(int(n)):
    value = int(input("{}{}{}".format("输入物品" , i ,"的价值：")))

maxvalue(int(n),int(m),weight,value)

测试用例：物品5件，背包容量6
                重量：1 2 3 4 5
                价值：2 4 4 5 6
打印dp数组不对：
[, , , , ]

陶远航 发表于 2023-8-9 17:24:12

这段代码中的问题在于初始化二维dp数组时，数组的行和列的数量没有正确设置。在创建dp数组时，应该要考虑到物品索引从0开始的特点。此外，还需要将背包容量m的范围扩展1个单位，以包括背包容量为0的情况。

以下是修改后的代码：

def maxvalue(n, m, weight, value):
    # 创建二维dp数组
    dp = [ for _ in range(n)]
   
    # 初始化第一行
    for j in range(weight, m+1):
      dp = value
   
    # 遍历
    for i in range(1, n):
      for j in range(1, m+1):
            if (j < weight[ i]):
                dp[ i] = dp
            else:
                dp[ i] = max(dp] + value[ i], dp)
   
    return dp


n = int(input("输入物品个数："))
m = int(input("输入背包容量："))
weight = * n
value = * n

for i in range(n):
    weight[ i] = int(input("输入物品{}的重量：".format(i)))
    value[ i] = int(input("输入物品{}的价值：".format(i)))

result = maxvalue(n, m, weight, value)
print(result)


修改后的代码会正确计算并输出01背包问题的结果。

希望这可以帮助到你！如果还有其他问题，请随时提问。
如果问题已经解决，请设置最佳答案

学习编程中的Ben 发表于 2023-8-9 17:24:12

Python 01背包问题

根据您提供的代码和测试用例，我注意到代码中存在一些小错误。我将为您提供修改后的完整代码：

def maxvalue(n, m, weight, value):
    # 创建二维dp数组，并初始化为0
    dp = [ for _ in range(n + 1)]

    # 遍历物品
    for i in range(1, n + 1):
      # 遍历背包容量
      for j in range(1, m + 1):
            # 当前物品重量大于背包容量，无法放入
            if weight > j:
                dp = dp
            else:
                # 考虑放入当前物品或不放入当前物品的情况
                dp = max(dp] + value, dp)

    return dp

n = int(input("输入物品个数："))
m = int(input("输入背包容量："))

weight = []
value = []

for i in range(n):
    weight.append(int(input(f"输入物品{i}的重量：")))

for i in range(n):
    value.append(int(input(f"输入物品{i}的价值：")))

result = maxvalue(n, m, weight, value)
print("最大价值：", result)


主要更改有：
1. 修正了dp数组大小为 (n+1) x (m+1)，因为物品和背包容量需要从1开始计数。
2. 在遍历物品和背包容量时，修改了索引的范围。
3. 将用户输入的物品重量和价值存储在列表中。

这样，您应该可以得到正确的结果了。如果还有其他问题，请随时提问。

如果回答对你有帮助，请给我一个最佳答案！{:10_254:}{:10_254:}{:10_254:}

isdkz 发表于 2023-8-9 17:24:18

问题出在创建二维dp数组时，数组的大小应该是(n+1) × (m+1)。因为dp[ i]表示在前i个物品中任拿，所能将容量为j的背包价值最大化，所以需要多一行和一列来表示没有物品和背包容量为0的情况。

修改后的代码如下：

def maxvalue(n, m, weight, value):
    # 创建二维dp数组
    dp = [ for j in range(n+1)]

    # 初始化
    for j in range(m+1):
      if j < weight:
            continue
      dp = value

    # 遍历
    for i in range(1, n+1):
      for j in range(m+1):
            # dp公式
            if j < weight:
                dp[ i] = dp
            else:
                dp[ i] = max(dp] + value, dp)
    print(dp)

n = int(input("输入物品个数："))
m = int(input("输入背包容量："))
weight = * n
value = * n
for i in range(n):
    weight[ i] = int(input("输入物品{}的重量：".format(i)))
for i in range(n):
    value[ i] = int(input("输入物品{}的价值：".format(i)))

maxvalue(n, m, weight, value)


运行修改后的代码，得到的dp数组为：

[, , , , , ]


可以看到dp数组的结果是正确的。

学习编程中的Ben 发表于 2023-8-9 17:56:04

给个最佳答案呗!求你了!!!{:10_254:}

15588686105 发表于 2023-8-9 18:13:52

谢谢各位老哥！
页: [1]
查看完整版本: python 的01背包结果有问题