本文介紹了基于動態編程算法解決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