Python动态规划实现01背包问题详解

Leo

发布时间：2026-10-13 | 4人浏览过

原创

本文通过Python实例演示如何利用动态规划算法解决01背包问题。文章详细阐述了状态转移逻辑，提供了自底向上的完整代码实现，包括价值计算与物品选择回溯，并展示了针对特定参数n=5、c=10的运行结果，帮助开发者理解重叠子问题的优化思路。

本文通过Python实例，详细讲解如何利用动态规划算法解决经典的01背包问题，内容供读者参考学习。

在01背包问题中，决策核心在于权衡是否将某物品放入背包。这需要比较“包含该物品”与“不包含该物品”两种情况下的子问题解，这种决策机制往往产生大量重叠子问题，因此采用动态规划是高效的解决策略。设定物品数量n=5，背包最大承重c=10，各物品重量数组w=[2,2,6,5,4]，价值数组v=[6,3,5,4,6]。首先确立递归定义的基础逻辑：

随后采用自底向上的方式构建解空间，具体实现代码如下：

def bag(n,c,w,v):
  res=[[-1 for j in range(c+1)] for i in range(n+1)]
  for j in range(c+1):
    res[0][j]=0
  for i in range(1,n+1):
    for j in range(1,c+1):
      res[i][j]=res[i-1][j]
      if j>=w[i-1] and res[i][j]<res[i-1][j-w[i-1]]+v[i-1]:
        res[i][j]=res[i-1][j-w[i-1]]+v[i-1]
  return res
def show(n,c,w,res):
  print('最大价值为:',res[n][c])
  x=[False for i in range(n)]
  j=c
  for i in range(1,n+1):
    if res[i][j]>res[i-1][j]:
      x[i-1]=True
      j-=w[i-1]
  print('选择的物品为:')
  for i in range(n):
    if x[i]:
      print('第',i,'个,',end='')
  print('')
if __name__=='__main__':
  n=5
  c=10
  w=[2,2,6,5,4]
  v=[6,3,5,4,6]
  res=bag(n,c,w,v)
  show(n,c,w,res)

程序运行输出结果如下所示：