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

文章介绍了使用动态规划方法解决背包问题，给定n件物品的重量和价值，以及一个最大背包容量，计算如何选择物品以使总价值最大。通过状态转移方程实现求解过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

有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 = 4

    result = solve(weight, value, bagweight)
    print(result)