【引言】有一個準(zhǔn)備偷東西的小偷，他有一個用來偷東西的背包做裙，這個背包只能裝4斤重的東西蜈首。但是他所要偷的店里实抡，卻有幾十種上百種的商品，這些商品質(zhì)量價格不一欢策，那么他該如何選擇才能偷到最好的一個物品集合使得他所偷取的東西總價最高呢吆寨？
動態(tài)規(guī)劃也是一種能將問題的規(guī)模縮小踩寇，解決了小問題啄清，逐漸的擴大問題規(guī)模就最終得到了問題的解答的這么一個算法。
算法過程
背包問題
如引言里所說俺孙，小偷偷東西的這種問題辣卒，就是背包問題。背包問題需要我們選擇出最好的一個物品組合來實現(xiàn)小偷偷東西的利益最大化睛榄。
問題規(guī)模
實際上荣茫，我們仔細(xì)思考這個問題的時候，可能腦海里第一個出來的方案就是把所有能偷的組合都列舉出來场靴，我們選擇其中背包能裝下的并且所偷物品價值最高的一個不就得了啡莉。但是，這樣做的代價是很高的旨剥。
對于小偷所要想偷的東西票罐，有N種，這N種就是一個可供選擇的集合泞边，小偷需要從中選擇一個子集來偷该押，含有N個元素的集合的子集的個數(shù)是：
這也就是說，隨著商品個數(shù)的增加阵谚，小偷需要考慮的偷取商品的幾何數(shù)量會指數(shù)級別的增長蚕礼，如果有 100 種商品，那么可以偷的情況就有 1267650600228229401496703205376 種梢什，小偷要想從這些中情況中選擇滿足背包重量要求的其中一個組合奠蹬，根本就無法列舉并抉擇。
動態(tài)規(guī)劃
我們跟著動態(tài)規(guī)劃算法的過程來看一下嗡午，動態(tài)規(guī)劃是怎么“動態(tài)”的規(guī)劃小偷該偷哪幾種東西囤躁。簡單一點，我們現(xiàn)在的問題變?yōu)椋⊥档谋嘲荒苎b4斤重的東西狸演，他可以偷的東西只有三種分別是：
此時背包容量只有4言蛇，要想拿走所有的東西，背包是裝不下的宵距，所以要有所取舍腊尚。我們使用動態(tài)規(guī)劃來進(jìn)行操作。所有商品的質(zhì)量（為了簡便）都是整數(shù)满哪，背包容量是4婿斥，我們就用所有商品質(zhì)量中的最小的分割單位(1斤)來對背包的容量進(jìn)行分割，形成一個以最小單位為列(背包容量是最大值)哨鸭，每件商品為行的一個表格：
接下來民宿，我們開始填充表格，在整個填充過程完成之后像鸡，我們就能得到最終的選擇結(jié)果了活鹰。
我們從上至下，從左至右的填充整個表格坟桅。首先來看第一排华望，第一排的意思是蕊蝗，小偷此時 只能選擇偷取Bose耳機 仅乓，小偷背包的最大容量是4，我們拆分開來蓬戚，假如我們分別拿出1夸楣、2、3子漩、4(最大)的容量來偷取Bose耳機豫喧，我們把每種容量偷取Bose耳機所能獲取的偷取商品的最大價值填入表格。
由于Bose耳機的質(zhì)量是1幢泼，所以紧显，當(dāng)背包容量是1的時候，小偷是可以偷取Bose耳機的缕棵，所以第一個格子我們填入Bose的價格3000：
繼續(xù)向后填寫孵班。第二個格子，此時背包容量是2招驴，但是小偷現(xiàn)在只能偷取Bose耳機篙程，盡管Bose耳機的質(zhì)量是1不能夠填滿背包。所以第二個格子還是只能裝一個Bose耳機别厘，同理背包容量是3虱饿、4此時在第一行都只能填入一個Bose耳機，于是我們就將表格的第一排都填充完畢了：
此時，圖表告訴我們的是氮发，如果我只能偷取Bose耳機這一種東西的話渴肉，當(dāng)背包容量為4的時候，我最多能偷取的物品的價值就是3000(一個Bose耳機)
繼續(xù)向下走折柠，我們開始填充第二排宾娜，第二排代表的是，此時扇售，小偷不僅能偷取Bose耳機前塔，還能夠偷取iPhone，而且小偷要優(yōu)先于iPone偷取 承冰。
首先是第二排的第一個位置华弓，此時背包容量是1。我們通過第一排知道困乒，目前為止寂屏，當(dāng)背包容量為1的時候，小偷所能偷取的最大的價值是3000娜搂。此時迁霎，因為iPhone的質(zhì)量是3，裝不下百宇，所以此時所能偷取的物品的最大價值還是3000：
同理考廉，第二個格子所能偷取的最大的價值也是3000。
此時來到了第三個格子携御，這個格子代表此時背包的容量為3昌粤，正好可以裝下iPhone。如果小偷此時裝下iPhone啄刹，那么這個格子的價值將是8000涮坐，比之前(上一行容量3的位置)的3000要高，所以小偷此時偷取的物品變?yōu)閕Phone誓军，價值變?yōu)?000:
到了第二排第四個格子袱讹，此時背包容量為4，小偷可以先裝入iPhone昵时，裝入了iPhone之后捷雕，背包容量被占用了3，還剩下1债查。此時小偷偷取了iPhone之后剩下的這1的容量還能裝入的最大價值的物品是哪些呢非区？這個答案要從第一排來找，因為第一排是除了iPhone之外剩下小偷所能偷的所有的商品的所對應(yīng)的不同容量下的最大價值盹廷。這時我們找到了征绸，當(dāng)容量為1(第二排的4容量裝了3容量的iPhone之后所剩下的)時，小偷能裝入背包的最大的價值就是第一排的第一個格子所記錄的3000！：
此時管怠，當(dāng)小偷手中只有一個容量為4的背包時淆衷，所能偷取的最大的物品的價值是11000。
最后一排渤弛。來到最后一排祝拯，這時，小偷能偷取的物品又多了一個iPad 她肯。
最后一排第一個格子佳头，當(dāng)背包容量為1的時候。由于iPad的質(zhì)量為4裝不下晴氨，所以康嘉，我們還是看它上一排，除了iPad之外所能裝在容量為1的背包中的最大的價值籽前，是3000亭珍，同理最后一排第二個跟第三個格子也是如此：
我們來到了最后一排的最后一個格子。此時背包容量為4枝哄，iPad的質(zhì)量也為4肄梨，iPad的價格是10000。當(dāng)小偷背包中不放iPad的時候(上一行的容量4的位置)挠锥，容量為4的背包所能裝的最大的商品價值是上一排代表容量為4的格子所填寫的11000众羡。11000 > 10000。也就是說如果背包此時不裝iPad瘪贱，改裝除了iPad之外其他的東西纱控，所能裝的最大的價值要比裝iPad要高辆毡。那么小偷就不裝iPad菜秦，繼續(xù)延續(xù)之前的選擇的物品：
至此，表格填充完畢舶掖。最后一個格子所代表的含義就是球昨，當(dāng)小偷可以選擇的商品有 Bose耳機、iPhone眨攘、iPad與此同時背包容量為4的情況下主慰，所能偷取的商品是Bose耳機、iPhone鲫售，總價值是11000共螺。
回顧一下最終的做出選擇的流程，我們總結(jié)一下規(guī)律：
對于每個格子情竹，填入格子中的值不外乎是這兩種中的一種：
既然保證利益最大化藐不，我們就取這兩種賦值方式中能得到的值較大的那個。這樣，我們整體的動態(tài)規(guī)劃的流程就結(jié)束了雏蛮。
動態(tài)規(guī)劃是將整個一個大問題零敲碎打涎嚼，分解成為背包容量分別為1、2挑秉、3法梯、4時候，物品分別為：Bose耳機犀概；Bose耳機立哑、iPhone；Bose耳機姻灶、iPhone刁憋、iPad這樣依次增加商品的情況下最終通過解決每個小格子，來使最終的這個大的格子所代表的問題得到解決木蹬。這樣做的好處在于如果我們此時再增加一個商品至耻，無非就是再多出一行來計算，最終也可以得到正確的結(jié)果镊叁！回顧一開始的假設(shè)尘颓，加入有100種商品，動態(tài)規(guī)劃所需要的計算步驟需要 4 × 100 = 400 < 1267650600228229401496703205376 晦譬，非嘲唐唬可觀。
算法實現(xiàn)
# -*- coding: utf-8 -*-
# @Time : 2019-03-19 09:17
# @Author : Jaedong
# @Version : 3.6
# @File : DynamicProgramming.py
# @Software: PyCharm
class Goods:
name = ''
price = 0
weight = 0
def __init__(self, name, price, weight):
self.name = name
self.price = price
self.weight = weight
def dynamic_programming(goods, min, max, step):
# 初始化分部計算的中間過程
steps = [[0 for col in range(min, max + 1, step)] for raw in range(len(goods))]
choosed = []
# 每一行的每一個格子(分開的步驟)
for i in range(len(goods)):
# 每一列的每一個格子(分開的步驟)
for j in range(min - step, max, step):
weight = goods[i].weight # 拿到當(dāng)前行的物品的重量
sameWeightMax = 0 # 初始化相同重量(同一列)上面已知的不包括本物品(本行物品)的最大的重量所裝物品的價值
currentStepPrice = goods[i].price # 當(dāng)前一行不同重量所能裝的最多物品的價值
# 為了防止越界敛腌，第一行要特殊處理卧土，非第一行的才走下面的賦值邏輯，其實也可以用哨兵
if i != 0:
sameWeightMax = steps[i - 1][j]
if j >= weight:
currentStepPrice = steps[i - 1][j - weight] + currentStepPrice
# 如果商品的重量小于等于背包的可以承受的重量像樊，那么就可以考慮是否應(yīng)該裝進(jìn)去尤莺， j+step是當(dāng)前步驟的重量
if weight <= j + step:
if sameWeightMax > currentStepPrice:
steps[i][j] = sameWeightMax
else:
steps[i][j] = currentStepPrice
else:
steps[i][j] = sameWeightMax
# 回溯一下，找到所包含的物品都有什么
choosed = []
colIndex = max - 1 # 減1之后代表的是下標(biāo)生棍，不減1代表重量
for i in range(len(goods) - 1, -1, -1):
good = goods[i]
if steps[i][colIndex] > steps[i-1][colIndex]:
choosed.append(goods[i].name)
colIndex = colIndex - good.weight
if colIndex >= 0: # 如果最終還有重量在的話（真實重量應(yīng)該+1）颤霎，這里避免了首個商品恰好是漏下沒有記錄的情況
choosed.append(goods[0].name)
return choosed
goods = [
Goods('Bose耳機', 3000, 1),
Goods('iPhone', 8000, 3),
Goods('MacBook Pro', 10000, 4)
]
# 這個示例是以重量為整數(shù)單位，如果涉及到小數(shù)涂滴，可以適當(dāng)?shù)倪M(jìn)行改版
choosed = dynamic_programming(goods, 1, 4, 1)
print('最終選擇的商品是：{}'.format(choosed))
結(jié)果是：
