0-1背包问题 动态规划及回溯过程 无基础详解 附python代码_py 回溯法算法过程与内存可视化(0-1背包问题为例)

0-1背包问题

N样物品，给定每样物品的重量wi和价值vi，装入容量为C的背包，如何装入背包使得其价值最大化？

举例

假设背包容量为8，有4样物品要装入，这4样物品的重量w和价值v分别为：

动态规划过程

设置一个二维数组DP[i][j]来记录动态规划过程中背包的最大价值。
数组的第一个下标i表示只有前i个物品可供装入背包，第二个坐标j表示动态规划过程中背包的容量，数组的值表示在这样的情况下背包的最大价值。
譬如，DP[3][6]代表在仅有物品1、2、3且背包容量为6的情况下，背包装入的最大价值是多少。

下面为动态规划数组DP[i][j]的初始情况，即在背包容量为0和未装入物品的情况下，背包装入的最大价值都只能为0。

在判断新的物品i是否可以加入时，可以借助上一横行即DP[i-1][...]的装入情况。设背包容量为j，

• 物品i不装入时，背包的装入情况和仅有物品0~i-1时相同，及DP[i][j] = DP[i-1][j]；
• 物品i装入时，背包相当于在仅有物品0~i-1且背包容量为j-wi的情况下又装入一个新的物品i（如下图），及DP[i][j] = DP[i-1][j-wi]+vi (j>=wi)，（其中wi是物品i的重量，vi是物品i的价值）。

据此可以设置状态转移方程：

根据状态转移方程填入动态规划数组DP[i][j]：

在本题中DP[4][8]就是我们最终要得到的背包最大价值。

回溯过程

通过以上步骤，我们已经得到了动态规划过程的二维数组。这一步回溯过程中，我们将通过动态规划二维数组得到每样物品在背包价值最大时是否装入背包。
由状态转移过程↑可以得知，

• 当新物品i未加入背包时，DP[i][j]=DP[i-1][j]；
• 当新物品i加入背包时，DP[i][j]>DP[i-1][j]。

因此比较DP[i][j]与DP[i-1][j]的大小就可以得到每样物品装入背包的情况。

注意：在判断出物品i加入背包后，应当把这样物品的重量从背包的容量减去

附python代码：

#函数输入 C：背包容量，w：物品重量，v物品价值
#   输出 背包最后装入的总价值，和代表每样物品是否装入的列表（True表示装入，False表示不装入）
def knapsack(C:int,w:list,v:list)->[int,list]:
    N=len(w)    #获得物品数量
    DP=[[0 for j in range(C+1)] for i in range(N+1)]    #获得一个(N+1)*(C+1)物品*容量的二维动态规划数组
    #动态规划过程
    for i in range(0,N):    #循环：物品i从0到N-1，步长1
        for j in range(0,C+1):    #循环：容量j从0到C，步长1
            if j<w[i]:
                DP[i+1][j]=DP[i][j]
            else:
                DP[i+1][j]=max(DP[i][j],DP[i][j-w[i]]+v[i])
    #回溯：获得背包内容，即每样物品是否加入背包
    knapsackContentList=[False for i in range(N)]   #获得一个长度为N的一维数组，代表各个物品是否装入背包
    tempCapacity=C	#背包剩余容量
    for i in range(N-1,-1,-1): #循环：i逆向从N-1到0，包括N-1和0，步长-1
        if DP[i+1][tempCapacity]>DP[i][tempCapacity]:	#判断该物品是否加入背包
            knapsackContentList[i]=True
            tempCapacity-=w[i]
    return DP[-1][-1],knapsackContentList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20