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

yipeiwu_com5年前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压缩解压缩zip文件及破解zip文件密码的方法

Python压缩解压缩zip文件及破解zip文件密码的方法

python 的 zipfile 提供了非常便捷的方法来压缩和解压 zip 文件。 例如,在py脚本所在目录中,有如下文件: readability/readability.js r...

python算法与数据结构之冒泡排序实例详解

python算法与数据结构之冒泡排序实例详解

一、冒泡排序介绍   冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地...

Python实现动态图解析、合成与倒放

Python实现动态图解析、合成与倒放

动态图现在已经融入了我们的日常网络生活,大大丰富了我们的表达方式和交流趣味性。常常是一言不合就扔动图,我这里就不举例子了,例子太多,平时大家也都接触过。咱们直接开始本文的内容。 用到的...

Pandas之排序函数sort_values()的实现

一、sort_values()函数用途 pandas中的sort_values()函数原理类似于SQL中的order by,可以将数据集依照某个字段中的数据进行排序,该函数即可根据指定列...

LRUCache的实现原理及利用python实现的方法

简介 LRU(Least Recently Used)最近最少使用,最近有时间和空间最近的歧义,所以我更喜欢叫它近期最少使用算法。它的核心思想是,如果一个数据被访问过,我们有理由相信它在...