假定我们一个拥有可以装4kg重东西的的背包。
以及有几件不同重量和价值的商品如下。
音响 3000￥ 4kg
笔记本电脑 2000￥ 3kg
吉他 1500￥ 1kg
每个动态规划都从一个网格开始，下方网格可以使用int类型数组来表示。
我们从第一行开始填写表格，由于从第一行我们只有吉他一个商品可供选择，
所以不管背包容量为多大，每个表格重填入的数据一定是1500￥如下图所示
第一行填入结束后，我们来看第二行。由于从第二行开始后我们可以装入的
商品就包括吉他和音响两个，所以我们需要在填写表格时考虑这两个商品的
可以装入的最大价值。
由于音响重4kg，所以我们在背包容量小于4kg时同样只能装入吉他，表格如
下所示。
当我们迭代到背包容量为4kg时，这时候我们的背包可以装入音响了，我们
判断是装入吉他价值高还是装入音响价值高，或是全部装入。但是显然我们
的背包容量只允许装入一个，所以我们选择价值更大的音响（3000￥）装入。
这时我们开始遍历最后一行——笔记本电脑。
笔记本电脑重量为3kg，当背包容量小于3kg时，我们依旧只能装入吉他。
这时我们遍历到容量为3kg时，很明显，我们应装入笔记本电脑，因为他
值2000￥。
这时我们遍历到最后容量为4kg时，这时很明显，我们发现吉他和笔记本
电脑的总重量为4kg且总价值为3500￥大于音响的3000￥，所以我们这时
应装入吉他和笔记本电脑。
我们先装入笔记本电脑，这时背包容量还剩余1kg，于是我们这时可以加上
一行背包容量为1kg时的商品即吉他。此时我们得到最终答案。
我们的得到的递推公式为
二维数组CELL即为本次使用的表格。
我们为当前单元格所填写的值为“上一行单元格的值”（CELL[i – 1][j]）与 “当前商品的价值 + 剩余空间的价值（CELL[i – 1][j – 当前商品的重量]）”两者中较大的那个。
总结
背包问题为动态规划类问题中非常经典的题目，很多动态规划问题都可通过变换转化为背包问题，或本身就是背包问题的变体。
使用动态规划的要点在于找到递推关系，动态规划的代码量一般很小，难点就在于递推关系的寻找。
结尾附上当前题目C语言代码
1 int main(void) 2 { 3 int c = 4; /*背包容量*/ 4 int p[3] = {1500, 3000, 2000}; /*商品价值*/ 5 int w[3] = {1, 4, 3}; /*商品重量*/ 6 int dp[4][c + 1]; /*数据表格*/ 7 8 for(int i = 0; i < 4; ++i) /*初始化表格*/ 9 { 10 for(int j = 0; j < c + 1; ++j) 11 { 12 dp[i][j] = 0; 13 } 14 } 15 16 for(int i = 1; i <= 3; ++i)/*动态规划 i为商品列表 j为当前背包容量*/ 17 { 18 for(int j = 1; j <= c; ++j) 19 { 20 if(j < w[i - 1])/*当前背包容量小于商品重量*/ 21 { 22 dp[i][j] = dp[i - 1][j]; 23 } 24 else/*当前背包容量大于等于商品重量*/ 25 { 26 /*三目运算符 将最大值赋值给当前格子*/ 27 dp[i][j] = dp[i - 1][j] > (dp[i - 1][j - w[i - 1]] + p[i - 1]) ? dp[i - 1][j] : (dp[i - 1][j - w[i - 1]] + p[i - 1]); 28 } 29 } 30 } 31 printf("%d\n", dp[3][4]);/*输出结果*/ 32 return 0; 33 }
图片与思路源自《算法图解》
原文地址：http://www.cnblogs.com/GYT-Blog/p/16923739.html
