Python基于动态编程算法处理了01背包问题的例子

本文介绍了基于动态编程算法解决01背包问题的Python示例. 与所有人共享以供参考，如下所示:

在01背包问题中，当选择是否向背包中添加物品时，必须将添加物品的子问题的解决方案与不携带物品的子问题的解决方案进行比较. 问题形成了许多重叠的子问题，这些问题可以使用动态编程解决. n = 5是物品的数量，c = 10是书包可以承受的重量，w = [2,2,6,5,4]是每个物品的重量，v = [6,3,5 ，4,6]是每个项目的值，首先写递归的定义:

然后从下至上实现它背包问题 动态规划 python，代码如下:

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编程有所帮助.

您可能感兴趣的文章: 最大子序列的python实现和（分而治之+动态编程）python实现的动态编程算法，用于解决最长的回文子串分析python动态编程的递归和非递归矩阵以进行动态编程连续乘法问题Python的Python实现方法基于动态编程算法来计算单词距离. 使用Python编写一个简单的彩票程序. Python + Redis实现Bloom过滤器. Python二次编程和线性编程示例

本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-286558-1.html