【代码随想录day25】动态规划：01背包理论基础

题目 

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 

代码

dp[i][j]: 表示从0~i个物品中选物品放到容量为j的背包中所能获得的最大价值

初始化: 第一列为0，第一行如果有容量>第一个物品重量的则赋值为第一个物品的价值

状态转移方程：dp[i][j]只能由上一个状态的背包“放”与“不放”物品i转移得出，选择“放”或“不放”第i个物品所能获得的最大值作为dp[i][j]的值，即dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

def solve(weight,value,bag_weight):# dp[i][j]表示从0~i个物品中选物品放到容量为j的背包中所能获得的最大价值dp = [[0]*(bag_weight+1) for _ in range(len(weight))]# 初始化第一列为0，第一行如果有容量>第一个物品重量的则赋值为第一个物品的价值for j in range(1,bag_weight+1):if j>=weight[0]:dp[0][j] = value[0]# dp[i][j]只能由上一个状态“放”与“不放”物品i转移得出for i in range(1,len(weight)):for j in range(1,bag_weight+1):dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])return dp[len(weight)-1][bag_weight]if __name__ == "__main__":weight = [1, 3, 4]value = [15, 20, 30]bagweight = 4result = solve(weight, value, bagweight)print(result)