您的位置:首页 > 技术干货 > Python基于动态规划算法解决01背包问题实例

Python基于动态规划算法解决01背包问题实例

来源:CDA数据分析师 | 发布时间:2018-05-15 06:05:06

Python基于动态规划算法解决01背包问题实例

本文实例讲述了Python基于动态规划算法解决01背包问题。分享给大家供大家参考,具体如下:

在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决。n=5是物品的数量,c=10是书包能承受的重量,w=[2,2,6,5,4]是每个物品的重量,v=[6,3,5,4,6]是每个物品的价值,先把递归的定义写出来:

然后自底向上实现,代码如下:

defbag(n,c,w,v):
  res=[[-1forjinrange(c+1)]foriinrange(n+1)]
  forjinrange(c+1):
    res[0][j]=0
  foriinrange(1,n+1):
    forjinrange(1,c+1):
      res[i][j]=res[i-1][j]
      ifj>=w[i-1]andres[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]
  returnres
defshow(n,c,w,res):
  print('最大价值为:',res[n][c])
  x=[Falseforiinrange(n)]
  j=c
  foriinrange(1,n+1):
    ifres[i][j]>res[i-1][j]:
      x[i-1]=True
      j-=w[i-1]
  print('选择的物品为:')
  foriinrange(n):
    ifx[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)

输出结果如下:


数据分析师 Python

分享到:

性别:

资料选取(每人只能选四项)

CDA考试指南
CDA数据分析员课程手册
CDA一级业务分析师课程手册
CDA二级建模分析师课程手册
CDA二级大数据分析师课程手册
CDA脱产就业班课程手册
CDA一级前导试听视频
CDA二级建模前导试听视频
CDA二级大数据前导试听视频
CDA招生简章及价格手册
软件下载指南
OK, 确定提交

就学教育 统计视频 论坛交流 CDA俱乐部 CDA协会 合作代理 官方微信
官方微博 QQ互动