動態規劃法

簡單說一下動態規劃的演算法流程

1. 填表

2. 獲取路徑

本文以下以0/1背包以及找零問題去說明動態規劃法

0/1背包里有：背包容量max_weight， 物品的重量 item_weights ,物品價值 item_values，當前背包容量current_bag_weight ，當前加入背包價值current_value

找零問題：應找的金額max_bill，自動售貨機擁有的內種硬幣的數量coins_count，每種硬幣的價值coin_values，當前已找金額current_bill，已找硬幣數量current_coins

item_weights = [w1, w2, w3, w4, w5]

item_values = [v1, v2, v3, v4, v5]

剛開始背包容量為max_weight，當前背包價值為0，我們可以稱這種狀態為狀態（0，max_weight），當前狀態下的價值為V(0, max_weight)

加入第一個物品時，第一個物品的重量為w1，價值為v1，所以我們從狀態(0，maxweight)轉移到了狀態（1，max_weight - w1）

在狀態轉移的時候我們需要判斷：

1、當前背包容量能否放入這個物品，current_weight >= w[i]

2、當前狀態加入這個物品後的價值是否有提升，即 max{ V(0, max_weight), V(1, max_weight - w[1]) }， 其中 V(1，maxweight - w[1]) = V(0, max_weight) + V[1]

如果上面兩個判斷中有一個是 False 的話，即不把第一個物品加入，下一狀態的價值等價於當前價值，以此類推到第n個物品。

那麼我們這個表有多少種狀態呢？

有max_weight * items.length種狀態

為什麼是這麼多種狀態呢？為什麼不是 max_weight-w[i]種不同的情況乘items.length呢？

個人理解是為了方便直接使用max_weight，而max_weight-w[i]情況太多，實現較為麻煩，所以乾脆不吝嗇那一點空間了。

好了，知道原理之後就可以開始填表了，從item=0，max_weight=0開始填充二維表，兩個for循環，即可把表填寫完畢，注意不要忘記判斷條件，以下是max_weight=8,item.length=4的部分代碼：

上圖為表填充後的狀態，至此動態規劃法的填表已經解決了

由0/1背包拓廣到找零問題:

max_weight < ==== > max_bill

items < ======= > coins

items_weight < ====== > coins_value

current_values < ===== > current_coins