【代码随想录day26】动态规划：01背包理论基础（滚动数组）

题目

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

代码 

二维背包转化成1维背包 

def solve(weight,value,bag_weight):
    n = len(weight)
    # dp[j]表示背包容量为j时所能获得价值
    dp = [0]*(bag_weight+1)
    
    # 遍历顺序是先物品后背包容量，不能反过来，不然每个位置只会选一个最大价值的物品
    for i in range(n):
        for j in range(bag_weight,weight[i]-1,-1):
            dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
    return dp[bag_weight]
    

if __name__ == "__main__":
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagweight = 4

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