背包問題
再看上一節的背包問題，假設你是一個小偷，背着一個可裝4磅東西的背包。
可盜竊的商品有3件。
簡單算法
最簡單的算法如下：嘗試各種可能的商品組合，并找出價值最高的組合。
這樣可行，但速度非常慢。在有3件商品的情況下，需要計算8種不同的集合；有4件商品時，需要計算16個集合。每增加一件商品時，需要計算的集合數都将翻倍。這種算法的運作時間為O(2^n)。
貪婪算法可以找到近似解，但是不能找到最優解。
動态規劃
對于背包問題，先決定小背包(子背包)問題，在逐漸解決原來的問題。
每個動态規劃算法都從一個網格開始，背包問題的網格如下：
網格的各行為商品，各列為不同容量(1~4磅)的背包。所有這些列你都需要，因為他們将幫助你計算子背包的價值。
網格最初是空的，你将填充其中的每個單元格，網格填滿後，就找到了問題的答案。
吉他行
這是吉他行，意味着你将嘗試将吉他裝入背包。在每個單元格，都需要做一個簡單的決定：偷不偷吉他？
第一個單元格表示背包的容量為1磅。吉他的重量也是一磅，這意味着它能裝入背包！是以這個單元格包含吉他，價值為1500美元。
與這個單元格一樣，每個單元格都将包含目前可裝入背包的所有商品。
這行的其他單元格也一樣，别忘了，這是第一行，隻有吉他可供選擇。換言之，假裝現在還沒有盜竊其他兩件商品。
動态規劃從小問題着手，逐漸解決大問題。這裡解決的子問題将幫助你解決的大問題。從圖中該行可得出，如果有一個容量4磅的背包，可在其中裝入的商品的最大價值為1500美元。
音響行
來填充下一行——音響行。現在處于第二行，可偷的商品有吉他和音響。在每一行，可偷的商品都為目前行的商品以及之前各行的商品。是以還不能偷筆記本電腦，而隻能偷音響和吉他。
先看第一個單元格，它表示容量為1磅的背包。在此之前，可裝入1磅背包的商品的最大價值為1500美元。
背包的容量為1，裝不下音響！由于容量1磅的背包裝不下音響，是以最大價值依然是1500美元。
接下來兩個單元格的情況依然如此。在這些單元格中，背包的容量分為2磅和3磅，而以前的最大價值為1500美元。
由于這些背包裝不下音響， 是以最大價值保持不變。背包容量為4磅才能裝下音響。原來最大價值為1500美元，但如果在背包裝入的是音響而不是吉他，價值将為3000美元。
在這個網格中，将逐漸地更新最大價值。
筆記本電腦行
下面以同樣的方式處理筆記本電腦。筆記本電腦中3磅，沒法将其裝入容量為1磅或2磅的背包，是以前兩個單元格的最大價值還是1500美元。
對于容量為3磅的背包，原來的最大價值為1500美元，但現在可選擇盜竊價值2000美元的筆記本電腦而不是吉他，這樣新的最大價值将為2000美元。
對于4磅的背包，這是非常重要的部分。目前最大價值為3000美元。但是筆記本的重量隻有3磅，還有1磅容量沒用！
在1磅的容量中，可裝入的商品的最大價值是1500，之前有計算過。是以需要看下音響 vs 筆記本和吉他。那邊價值更高。
最終的網格類似如下
答案如下：将吉他和筆記本電腦裝入背包時價值最高，為3500美元。
你可能認為，計算最後一個單元格的價值，使用了不同的公式。那是因為填充之前的單元格時，故意避開了一些複雜的因素。其實，計算每個單元格的價值時，使用的公式都相同，公式如下：