AcWing 2. 01背包问题(pytho3解法)
原题链接
简单
作者:
PandaWaKaKa
,
2019-08-25 12:33:53
,
所有人可见
,
阅读 8064
解法1:二维dp
n, v = map(int, input().split())
goods = []
for i in range(n):
goods.append([int(i) for i in input().split()])
# 初始化,先全部赋值为0,这样至少体积为0或者不选任何物品的时候是满足要求
dp = [[0 for i in range(v+1)] for j in range(n+1)]
for i in range(1, n+1):
for j in range(1,v+1):
dp[i][j] = dp[i-1][j] # 第i个物品不选
if j>=goods[i-1][0]:# 判断背包容量是不是大于第i件物品的体积
# 在选和不选的情况中选出最大值
dp[i][j] = max(dp[i][j], dp[i-1][j-goods[i-1][0]]+goods[i-1][1])
print(dp[-1][-1])
解法2:一维dp
n, v = map(int, input().split())
goods = []
for i in range(n):
goods.append([int(i) for i in input().split()])
dp = [0 for i in range(v+1)]
for i in range(n):
for j in range(v,-1,-1):
if j >= goods[i][0]:
dp[j] = max(dp[j], dp[j-goods[i][0]] + goods[i][1])
print(dp[-1])
谢谢大佬,在力扣做了好久py就是不知道io怎么写,学到了
怎么运行完是错的
python竞赛不可以用
面试可以python吗
搞了小半天第一种解法终于懂了
可以帮忙解释一下吗 看不懂 哭了
推荐你看一下算法图解的动态规划,模拟一下,然后再看y总讲的就很清晰了
日狗,看不懂
大佬您好,请问为什么
dp[j] = max(dp[j], dp[j-goods[i][0]] + goods[i][1])
可以按需求筛选出最大价值呢。断点跑了一遍没有看懂您好,想请教下,在控制流输入时如下输入为什么不可以呢?
def get_max_value(n, v):
dp = [[0 for _ in range(v)] for _ in range(n)]
for i in range(n):
for j in range(v):
if j >= v[i]:
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])
return f[n][v]
if name == “main”:
no1 = input().split()
n, v = int(no1[0]), int(no1[1])
v = [0 for _ in range(n)]
w = [0 for _ in range(n)]
for i in range(n):
v[i], w[i] = int(input().split()[0]), int(input().split()[1])
print(get_max_value(n, v))