0-1背包問題：有一個賊在偷竊一家商店時，發現有n件物品，第i件物品價值vi元，重wi磅，此處vi與wi都是整數。他希望帶走的東西越值錢越好，但他的背包中至多隻能裝下W磅的東西，W為一整數。應該帶走哪幾樣東西？這個問題之是以稱為0-1背包，是因為每件物品或被帶走；或被留下；小偷不能隻帶走某個物品的一部分或帶走同一物品兩次。
在分數（部分）背包問題（fractional knapsack problem)中，場景與上面問題一樣，但是竊賊可以帶走物品的一部分，而不必做出0-1的二分選擇。可以把0-1背包問題的一件物品想象成一個金錠，而部分問題中的一件物品則更像金沙。
兩種背包問題都具有最優子結構性質。對0-1背包問題，考慮重量不超過W而價值最高的裝包方案。如果我們将商品j從此方案中删除，則剩餘商品必須是重量不超過W-wj的價值最高的方案（小偷隻能從不包括商品j的n-1個商品中選擇拿走哪些）。
雖然兩個問題相似，但我們用貪心政策可以求解背包問題，而不能求解0-1背包問題，為了求解部分數背包問題，我們首先計算每個商品的每磅價值vi/wi。遵循貪心政策，小偷首先盡量多地拿走每磅價值最高的商品，如果該商品已全部拿走而背包未裝滿，他繼續盡量多地拿走每磅價值第二高的商品，依次類推，直到達到重量上限W。是以，通過将商品按每磅價值排序，貪心算法的時間運作時間是O(nlgn)。
為了說明貪心這一貪心政策對0-1背包問題無效，考慮下圖所示的問題執行個體。此例包含3個商品和一個能容納50磅重量的背包。商品1重10磅，價值60美元。商品2重20磅，價值100美元。商品3重30磅，價值120美元。是以，商品1的每磅價值為6美元，高于商品2的每磅價值5美元和商品3的每磅價值4美元。是以，上述貪心政策會首先拿走商品1。但是，最優解應該是商品2和商品3，而留下商品1。拿走商品1的兩種方案都是次優的。
但是，對于分數背包問題，上述貪心政策首先拿走商品1，是可以生成最優解的。拿走商品1的政策對0-1背包問題無效是因為小偷無法裝滿背包，空閑空間降低了方案的有效每磅價值。在0-1背包問題中，當我們考慮是否将一個商品裝入背包時，必須比較包含此商品的子問題的解與不包含它的子問題的解，然後才能做出選擇。這會導緻大量的重疊子問題——動态規劃的辨別。
例子：0-1背包問題。總共有三件物品，背包可容納5磅的東西，物品1重1磅，價值60元。物品2重2磅，價值100元，物品3重3磅，價值120元。怎麼才能最大化背包所裝物品的價值。
解答：我們可以得出物品一每磅價值60元，大于物品二的每磅50元和物品3的每磅40元。如果按照貪心算法的話就要取物品1。然而最優解應該取的是物品2和3，留下了1.
在0-1背包問題中不應取物品1的原因在于這樣無法将背包填滿，空餘的空間就降低了貨物的有效每磅價值。
我們可以利用動态規劃來解0-1背包問題。
假設c[i]表示第i件物品的重量，w[i]表示第i件物品的價值，f[i][j]表示背包容量為j,可選物品為物品1~i時，背包能獲得的最大價值。
用動态規劃求解即先求出背包容量較小時能獲得的最大價值，然後根據背包容量較小時的結果求出背包容量較大時的結果，也就是一個遞推的填表過程。
當沒有可選物品時，背包能獲得的最大價值為0。即表格可初始化為
"j<c[i]"表示第i件物品的重量大于目前背包的容量j，此時顯然不放第i件物品。下面解釋上述方程在“其它“情況下的意義：”将前i件物品放入容量為j背包中“這個問題，如果隻考慮第i件物品放或者不放，那麼就可以轉化為隻涉及前i-1件物品的問題，即：
1. 如果不放第i件物品，則問題轉化為隻涉及”前i-1件物品放入容量為j的背包中“
2. 如果放第i件物品，則問題轉化為”前i-1件物品放入剩下的容量為j-c[i]的背包中“，此時能獲得的最大價值就是f[i-1][j-c[i]]再加上通過放入第i件物品獲得的價值獲得的價值w[i]。
則在”其他“情況下，f[i][j]就是1、2中最大的那個值。
顯然，可以從左下角利用狀态轉移方程依次逐行填表，得到f[3][5]（表示可選物品為1、2、3，且背包容量為5時，能獲得的最大價值），可見動态規劃的确即為一個遞推的過程。填表後如下表所示：
int N = 3, V = 5; //N是物品數量，V是背包容量
int c[4] = {0,1,2,3};
int w[4] = {0.60.100.120};
for (i = 0; i <= V; i++) { //逐行填表，i表示目前可選物品數，j表示目前背包的容量
f[i][0] = 0;
for (j = 1; j <= V; j++) {
if (j < c[i]) {
f[i][j] = f[i-1][j];
} else {
f[i][j] = max(f[i-1][j], f[i-1][j-c[i]] + w[i]);
}
}
}
背包問題初始化
求最優解的背包問題中，事實上有兩種不太相同的問法。有的題目要求”恰好裝滿背包“時的最優解，有的題目則沒有要求必須把背包裝滿。這兩種問法的差別是求解時的初始化不同。
如果是第一種問法，要求恰好裝滿背包，那麼在初始化時除了f[0][0]為0，其他f[0][1~V]均設為－∞ ，這樣就可以包裝最終得到的解釋一種恰好裝滿背包的最優解。
如果并沒有要求必須是把背包裝滿，而是隻希望價格盡量大，初始化時應該将f[0][1~V]全部設為0.
這是為什麼呢？可以這樣了解：初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀态。如果要求背包恰好裝滿，那麼此時隻有容量為0的背包可以在什麼也不裝且價值為0的情況下被”恰好裝滿“，其他容量的背包均沒有合法的解，屬于未定義的狀态，應該被指派為－∞。如果背包并非被必須裝滿，那麼任何容量的背包都有一個合法解”什麼都不裝“，這個解的價值為0，是以初始狀态的值也就全部為0了。