Python动态规划解决0-1背包问题详解

南乔

发布时间：2026-10-14| 5人浏览过

原创

本文介绍如何使用Python通过动态规划算法解决0-1背包问题。文章详细解析了状态转移方程的构建、最大价值的计算逻辑以及物品选择的回溯过程，并提供了完整的代码实现与优化方案，帮助开发者理解并应用该经典算法。

问题定义与参数设置

假设有一个最大承重为4kg的背包，现有四件物品可供选择。这些物品的重量分别为1kg、4kg、3kg和1kg，对应的价值依次为1500、3000、2000和2000。

目标是在不超过背包最大载重量的前提下，选择放入包内的物品组合，使得总价值最大化。

动态规划核心算法实现


#几件物品的重量
w = [0,1,4,3,1]
#几件物品的价值
v= [0, 1500, 3000, 2000, 2000]
#物品数量
n = len(w) - 1
#包的载重量
m = 4
 
#建立一个列表表示在包中的物品，元素是True时代表对应元素放入
x = [] 
#放入包中的总价值
value = 0
#建立一个矩阵，来表示在前i个物品中，当载重量是j时，放入包中的最大价值，table[i][j]
table = [[0 for i in range(m+1)] for j in range(n+1)]
 
def dynamic(w,v,n,m,x):
 #计算table矩阵
 for i in range(1, n+1): #代表物品一件一件的考虑
  for j in range(1, m+1):  #代表子背包的大小一点一点的考虑
   if (j >= w[i]): #当背包的大小大于物品的重量时，考虑放进去
    table[i][j] = max(table[i-1][j], table[i-1][j-w[i]] + v[i])
   else:
    table[i][j] = table[i -1][j] #如果放不进去，就继承之前的价值
    
 #递推装入背包中的物体，寻找跳变的地方，从最后结果开始逆推
 j = m
 for i in range(n, 0, -1):
  if table[i][j] > table[i- 1][j]: #如果多加一件物品之后，价值增大，就将这一件物品加入列表中
   x.append(i)
   j = j - w[i] #此时为剩余背包的载重量
   
 #返回最大价值，即表格中最后一行最后一列的值
 value = table[n][m]
 return value
 
print("最大价值为：", str(dynamic(w, v, n, m, x)))
print("物品的索引：", x)

以下是使用Python实现动态规划解决背包问题的具体代码示例。

基于NumPy的优化实现


import numpy as np
def bag(weight,values,weight_cont):
 num = len(weight)
 weight.insert(0,0)
 values.insert(0,0)
 bag = np.zeros((num+1,weight_cont+1),dtype=np.int)
 for i in range(1,num+1):
  for j in range(1,weight_cont+1):
   if j >= weight[i]:
    bag[i][j] = max(bag[i-1][j],bag[i-1][j-weight[i]]+values[i])
   else:
    bag[i][j] = bag[i][j-1]
 return bag[-1][-1]
if __name__ == '__main__':
 weight = [1, 2, 4, 10, 12]
 values = [1200, 1500, 2000, 1300, 2500]
 weight_cont = 20
 re = bag(weight,values,weight_cont)
 print(re)

以上就是关于Python实现动态规划背包问题的详细介绍。如需了解更多相关技术内容，欢迎查阅本站历史文章或继续浏览后续更新。感谢大家的支持！