歡迎點(diǎn)擊「算法與編程之美」↑關(guān)注我們！

本文首發(fā)于微信公眾號(hào)："算法與編程之美"，歡迎關(guān)注，及時(shí)了解更多此系列文章。

歡迎加入團(tuán)隊(duì)圈子！與作者面對(duì)面！直接點(diǎn)擊！

前言

對(duì)學(xué)算法的同學(xué)來說，動(dòng)態(tài)規(guī)劃是其必學(xué)且較為重要的問題之一；其中0-1背包問題是最經(jīng)典的動(dòng)態(tài)規(guī)劃問題；本博客也主要以動(dòng)態(tài)規(guī)劃來解決0-1背包問題。

問題描述

有如下的背包的重量及其所對(duì)應(yīng)的質(zhì)量，背包的最大承受重量為6kg，試問要怎樣裝入才能使得背包再最大的承受重量的范圍內(nèi)裝入的物品的質(zhì)量最大？

物品序號(hào)

1

2

3

4

重量

3kg

1kg

2kg

4kg

質(zhì)量

6￥

10￥

5￥

10￥

動(dòng)態(tài)規(guī)劃進(jìn)行問題分析

首先我們的創(chuàng)一個(gè)dp[i][j]的數(shù)組，bag[index]數(shù)組表示物品的重量與質(zhì)量；

(bag[index][0]表示重量，bag[index][1]表示質(zhì)量)；其中的i來表示物品，j來表示當(dāng)前背包所能承受的最大重量；dp[i][j]來表示當(dāng)前背包重量為j時(shí)所能承裝的最大質(zhì)量，這時(shí)我們可以等到一個(gè)動(dòng)態(tài)的轉(zhuǎn)移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-bag[index][0]]+bag[index][1])

方程解析；當(dāng)我們?nèi)ケ闅v物品的時(shí)候我們會(huì)分兩種情況，即裝與不裝；

不裝入該物品：dp[i][j]的質(zhì)量就是上個(gè)物品的質(zhì)量，即就等于dp[i-1][j]；i表示物品，就是i-1的質(zhì)量。

裝入該物品：dp[i-1][j-bag[index][0]]+bag[index][1]，i表示當(dāng)前的第i個(gè)物品，i-1表示上一個(gè)物品，因?yàn)閖表示當(dāng)前背包所能承裝的最大質(zhì)量，所以j-bag[index][0]表示若要裝入物品，那么必須取上一個(gè)物品的背包最大容量(即第i-1個(gè)物品)為j-bag[index][0]，因?yàn)檫@樣裝入第i個(gè)物品剛好裝滿容量為j的背包。

代碼解決

bag, n, dp = [[6,3],[10,1],[5,2],[10,4]], 6, []

# bag表示物品的重量與其所對(duì)應(yīng)的質(zhì)量，n為背包最大容量

for i in range(len(bag)): dp.append([0]*(n+1))

for i in range(n+1):

if i >= bag[0][1]: dp[0][i] = bag[0][0]

#第一次遍歷數(shù)組將得到第一個(gè)物品所對(duì)應(yīng)的最大質(zhì)量得出

for i in range(1,len(bag)):

for j in range(n+1):

if bag[i][1] <= j:

dp[i][j] = max(dp[i-1][j], dp[i-1][j-bag[i][1]]+bag[i][0])

# 取dp[i][j]當(dāng)前的最大質(zhì)量

print(dp[-1][-1]) # 打印dp最終j=n(背包最大容量)的最大質(zhì)量

總結(jié)

本博客主要講述了如何用動(dòng)態(tài)規(guī)劃來解決0-1背包問題；總的來說，0-1背包問題就是經(jīng)典的動(dòng)態(tài)規(guī)劃問題，用dp數(shù)組來記憶所需的值來推導(dǎo)相關(guān)聯(lián)的下一個(gè)值即可。

END

編 輯 | 王 文 星

責(zé) 編 | W Z Y

能力越強(qiáng)，責(zé)任越大。實(shí)事求是，嚴(yán)謹(jǐn)細(xì)致。

——where2go 團(tuán)隊(duì)

---

微信號(hào)：算法與編程之美

長按識(shí)別二維碼關(guān)注我們!

溫馨提示：點(diǎn)擊頁面右下角“寫留言”發(fā)表評(píng)論，期待您的參與！期待您的轉(zhuǎn)發(fā)！