1、01背包問題
有N件物品和一個容量為V的背包，第i件物品的體積是c[i]，價值是w[i]。求解将哪些物品裝入背包可使價值總和最大。
解析：
這是最基礎的背包問題，特點是每種物品僅有一件，可以選擇放或不放。用子問題定義狀态，即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。其狀态轉移方程便是f[i][v] = max{f[i-1][v], f[i-1][v-c[i]]+w[i]}，這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的，是以有必要将它詳細解釋一下：“将前i件物品放入容量為v的背包中”這個子問題，若隻考慮第i件物品的政策（放或不放），那麼就可以轉化為一個隻關系前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為“前i-1件物品放入容量為v的背包中”，其價值為f[i-1][v]；如果放第i件物品，那麼問題就轉化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。
算法實作：
(1)二維數組實作背包
結果輸出：
(2)一維數組實作背包
總結：
動态規劃的核心是狀态和狀态轉移方程。01背包問題是最基本的背包問題，它包含了背包問題中狀态、方程的最基本思想，另外，别的類型的背包問題往往也可以轉換成01背包問題求解。