01背包问题

系统管理员 2022-09-10 11:27 153阅读 0赞

# 1.题目 #

有N件物品和一个容量为V的背包。第i件物品的成本是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大，要求是：物品只能放一次。

# 2.分析 #

写动态规划题，需要抓住三点：做好状态假设；并推导出转换条件；

假设`dp[i][j]` 表示放当前第i件物品，在总质量为j的情况下，可以得到的最大价值，当前物品只有放与不放两种选择，如果选择放，那么就相当于从j个质量中腾出w\[i\]个质量给第i个物品；如果选择不放，那么就相当于直接“继承”第i-1件物品的最大值。  
所以根据上面这两点，我们可以得到如下表达式：  
 d p \[ i \] \[ j \] = \{ d p \[ i − 1 \] \[ j \] i f ( j < w \[ i \] ) d p \[ i − 1 \] \[ j − w \[ i \] \] + c \[ i \] i f ( j ≥ w \[ i \] ) dp\[i\]\[j\]=\\left\\\{\\begin\{aligned\} &dp\[i-1\]\[j\] \\quad \\quad if(j < w\[i\])\\\\ &dp\[i-1\]\[j-w\[i\]\]+c\[i\] \\quad if(j \\ge w\[i\]) \\end\{aligned\} \\right. dp\[i\]\[j\]=\{ dp\[i−1\]\[j\]if(j<w\[i\])dp\[i−1\]\[j−w\[i\]\]\+c\[i\]if(j≥w\[i\])  
根据这个式子，就可以写出整个代码了。

# 3.示例 #

各个物品的重量w = \[1,3,2,5\]，各个物品的金钱p = \[200,240,140,150\]，背包所能承受的最大重量 5。那么所能得到的最大价值是什么？

# 4.代码 #

def pack_01(w,c,maxW):
        # f = [0 for i in range(4) for j in range(5)] # 生成的是一位数组
        # 第一个是行，第二个是列
        f = [[0 for _ in range(6)] for _ in range (5)]
    
        for i in range(1,5): # i表示当前物品 [1,5)
            for j in range(1,maxW+1): # j表示当前重量 [5,0)
                f[i][j] = f[i-1][j] # 首先初始化赋值，这是最基本的
                if j >= w[i]:
                    f[i][j] = max(f[i][j],f[i-1][j-w[i]] + c[i]) # 取最大 
        print(f[4][maxW])
    
    # 为了方便，0下标被置为0
    w = [0,1,3,2,5] 
    c = [0,100,240,140,150]
    maxW = 5 # 能承受的最大重量
    pack_01(w,c,5)