Python实现动态规划中的01背包问题

对于动态规划问题，就是牺牲空间来提高时间，通过将一个个小问题的答案存储起来，直接供给后面问题求解，避免重复的运算，从而提高效率，这就是动态规划的思想。

下面我们通过一个经典的01背包问题来了解动态规划的解题方法吧（文末附上完整代码）

首先，将每个物品的体积以及价值存放在列表中，代码和运行结果如下：

可以看到，我们将三个物品信息放入列表中，第一个元素用[0,0]占位，使列表下标就是物品对应的序号，便于我们对代码的理解。

接下来我们将列表arr和背包容量bag传入函数进行运算，函数代码如下：

首先创建一个列表value，一共(bag+1)列，len(arr)行，先全部填充为0

该表格即为在不同背包容量下的物品价值表，0行即为前零个物品放入背包的价值，所以为0。1行为第一个物品放入背包的价值。二行为物品一和物品二放入背包的情况。3行即为物品一二三放入背包的情况。最大价值就如表中为9的单元格，对应的就是背包容量为五，考虑三个物品放入的最大价值。

对于画出这样的一个价值表，我们就得找出他的状态转移方程，这里我们利用代码中定义的数据来进行解释：

                我们传入的arr[]列表包含了N个物品，每个物品的下标从1-N，物品包含两个数据，一个为体积，一个为价值。例如[1，2]，1为体积，2为价值。我们就可以通过下标访问每个物品的体积与价值。

                我们用循环遍历来对列表value赋值，用i控制行，j控制列（i，j都是从1开始）

                对于物品放入的情况有两种，当j(背包容量)<第i个物品的体积时，第i个物品无法放入背包，所以最大价值就是在该容量下放入前（i-1）物品的价值，此时有方程：

                value[i][j]=value[i-1][j]                                （1）

                当背包容量大于i的体积时，可以放入i号物品，此时最大价值为

                 value[i][j]=max(value[i-1][j],value[i-1][j-arr[i][0]]+arr[i][1]）        （2）

                对于这个方程的解读，我的理解是：选择如（1）式不放入i，或者放入i时的最大值。对于放入i的公式解读如下：

                若要放入i,则需要留出i对应的空间大小arr[i][0]（留出空间后的空间大小为：j-arr[i][0]）,此时剩下的空间放前（i-1）个物品，便可以通过查表读取前i-1个物品在j-arr[i][0]背包容量下的最大价值，再加上i物品的价值arr[i][1],即使加入i物品的价值，再与value[i-1][j]比较，填入较大的一个。

最后创建的最大价值列表如下：（第二栏）

完整代码如下：

def backpack(arr,bag):        #创建在不同物品和背包容量下能装物品最大价值表
    value = [[0 for j in range(bag+1)] for i in range(len(arr))]#先全部填入0
    #第一行第一列为0，意思是在0个物品或0容量背包下总价值为0
    for i in range(1,len(arr)):
        for j in range(1,bag+1):
            if j<arr[i][0]:
                value[i][j]=value[i-1][j]
            else:
                value[i][j]=max(value[i-1][j],value[i-1][j-arr[i][0]]+arr[i][1])
    return value        #返回所有组合的价值表

wupin=[]
arr=[[0,0]]
N=int(input("请输入物品个数N："))
bag=int(input("请输入背包容量（kg）："))
for i in range(N):
    zf = input(f"请输入第{i+1}个物品信息：（体积 价值）")
    mass = zf.split(' ')
    for j in mass:
        j= int(j)
        wupin.append(j)
    arr.append(wupin)           #创建一个列表，对应每一个物品信息
    wupin = []
print(arr)              #打印物品信息列表

value=backpack(arr,bag)
print(value)

有不足之处，还望指正！