|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#n种物品,每种物品只有一件 物品只有拿不拿两种状态
#dp[i][j]:在[0,i]物品中任拿,所能将容量位j的背包价值最大化
#dp[i][j]=max(dp[i-1][j-wei[i]]+val[i],dp[i-1][j])
def maxvalue(n,m,weight,value):
# 创建二维dp数组
dp= [[0 for i in range(m)]for j in range(n)]
# 初始化
for j in range(m):
if j < weight[0]:
continue
dp[0][j] = value[0]
# 遍历
for i in range(1,n):
for j in range(m):
# dp公式
if(j < weight[i]):
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j - weight[i]] + value[i],dp[i - 1][j])
# return dp[n-1][m-1];
print(dp)
n=input("输入物品个数:") # input返回str型
m=input("输入背包容量 ")
weight=[0] * int(n)
value=[0] * int(n)
for i in range(int(n)):
weight[i] = int(input("{}{}{}".format("输入物品" , i ,"的重量:")))
for i in range(int(n)):
value[i] = int(input("{}{}{}".format("输入物品" , i ,"的价值:")))
maxvalue(int(n),int(m),weight,value)
测试用例:物品5件,背包容量6
重量:1 2 3 4 5
价值:2 4 4 5 6
打印dp数组不对:
[[0, 2, 2, 2, 2, 2], [0, 2, 4, 6, 6, 6], [0, 2, 4, 6, 6, 8], [0, 2, 4, 6, 6, 8], [0, 2, 4, 6, 6, 8]]
Python 01背包问题
根据您提供的代码和测试用例,我注意到代码中存在一些小错误。我将为您提供修改后的完整代码: def maxvalue(n, m, weight, value): # 创建二维dp数组,并初始化为0 dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)] # 遍历物品 for i in range(1, n + 1): # 遍历背包容量 for j in range(1, m + 1): # 当前物品重量大于背包容量,无法放入 if weight[i - 1] > j: dp[i][j] = dp[i - 1][j] else: # 考虑放入当前物品或不放入当前物品的情况 dp[i][j] = max(dp[i - 1][j - weight[i - 1]] + value[i - 1], dp[i - 1][j]) return dp[n][m]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. 将用户输入的物品重量和价值存储在列表中。
这样,您应该可以得到正确的结果了。如果还有其他问题,请随时提问。
如果回答对你有帮助,请给我一个最佳答案!
|
|