欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python基于動態(tài)規(guī)劃算法解決01背包問題實例

 更新時間：2017年12月06日 12:26:10   作者：littlethunder  
這篇文章主要介紹了Python基于動態(tài)規(guī)劃算法解決01背包問題,結(jié)合實例形式分析了Python動態(tài)規(guī)劃算法解決01背包問題的原理與具體實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了Python基于動態(tài)規(guī)劃算法解決01背包問題。分享給大家供大家參考，具體如下：

在01背包問題中，在選擇是否要把一個物品加到背包中，必須把該物品加進(jìn)去的子問題的解與不取該物品的子問題的解進(jìn)行比較，這種方式形成的問題導(dǎo)致了許多重疊子問題，使用動態(tài)規(guī)劃來解決。n=5是物品的數(shù)量，c=10是書包能承受的重量，w=[2,2,6,5,4]是每個物品的重量，v=[6,3,5,4,6]是每個物品的價值，先把遞歸的定義寫出來：

然后自底向上實現(xiàn)，代碼如下：

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)

輸出結(jié)果如下：

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》

希望本文所述對大家Python程序設(shè)計有所幫助。

相關(guān)文章

最新評論