编程题之背包问题

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)