编程题之背包问题
程序员文章站
2022-07-15 18:47:58
...
01背包问题
# 示列 1
# 输入
"""
5 10
8 6
10 4
4 2
5 4
5 3
"""
# 输出
"""
19
"""
# 示列 2
# 输入
"""
1 1
10 2
"""
# 输出
"""
0
"""
代码
# 01背包模板题
def solve(weight,value, n, m):
#
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,m+1):
if j-weight[i-1]>=0:
# 不选当前商品,选当前商品
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1])
else:
dp[i][j] = dp[i-1][j]
print(dp[-1][-1])
# 优化
dp = [0] * (m + 1)
# weight代表物品的重量
# value代表物品的价值
for i in range(1, len(value)+1):
for j in range(m, 0, -1):
if j-weight[i-1]>=0:
dp[j] = max(dp[j],dp[j-weight[i-1]]+value[i-1])
print(max(dp))
print(dp[m])
if __name__ == '__main__':
n, m = map(int, input().split())
weight = []
value = []
for _ in range(n):
v, w = list(map(int, input().split()))
weight.append(w)
value.append(v)
solve(weight, value, n, m)