对于动态规划问题，就是牺牲空间来提高时间，通过将一个个小问题的答案存储起来，直接供给后面问题求解，避免重复的运算，从而提高效率，这就是动态规划的思想。
下面我们通过一个经典的01背包问题来了解动态规划的解题方法吧（文末附上完整代码）
首先，将每个物品的体积以及价值存放在列表中，代码和运行结果如下：
可以看到，我们将三个物品信息放入列表中，第一个元素用[0,0]占位，使列表下标就是物品对应的序号，便于我们对代码的理解。
接下来我们将列表arr和背包容量bag传入函数进行运算，函数代码如下：
首先创建一个列表value，一共(bag+1)列，len(arr)行，先全部填充为0
| 物品 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 2 | 3 | 5 | 5 | 5 |
| 3 | 0 | 2 | 4 | 6 | 7 | 9 |
该表格即为在不同背包容量下的物品价值表，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)有不足之处，还望指正！
文章来源地址https://www.toymoban.com/news/detail-461477.html
文章来源：https://www.toymoban.com/news/detail-461477.html
到了这里，关于动态规划-01背包问题（python）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
