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

yipeiwu_com7年前Python基础

本文实例讲述了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)

输出结果如下:

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

相关文章

Python如何获得百度统计API的数据并发送邮件示例代码

小工具 本来这么晚是不准备写博客的,当是想到了那个狗子绝对会在开学的时候跟我逼逼这个事情,所以,还是老老实实地写一下吧。 Baidu统计API的使用 系统环境: Python2...

python 调用c语言函数的方法

虽然python是万能的,但是对于某些特殊功能,需要c语言才能完成。这样,就需要用python来调用c的代码了 具体流程: c编写相关函数 ,编译成库 然后在python中加载这些...

python设置检查点简单实现代码

说检查点,其实就是对过去历史的记录,可以认为是log.不过这里进行了简化.举例来说,我现在又一段文本.文本里放有一堆堆的链接地址.我现在的任务是下载那些地址中的内容.另外因为网络的问题或...

Python图像处理之图像的读取、显示与保存操作【测试可用】

Python图像处理之图像的读取、显示与保存操作【测试可用】

本文实例讲述了Python图像处理之图像的读取、显示与保存操作。分享给大家供大家参考,具体如下: python作为机器学习和图像处理的利器,收到越来越多的推崇,特别是在图像处理领域,越来...

结合OpenCV与TensorFlow进行人脸识别的实现

结合OpenCV与TensorFlow进行人脸识别的实现

作为新手来说,这是一个最简单的人脸识别模型,难度不大,代码量也不算多,下面就逐一来讲解,数据集的准备就不多说了,因人而异。 一. 获取数据集的所有路径 利用os模块来生成一个包含所有数据...