接下来看一个动态规划的经典问题:0-1背包问题  

问题描述：

   给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

这个问题确实是要困难一些，首先这个状态就不是很好确定，由于个额外的条件，背包容量有限，所以要兼顾考虑两个因素的限制，一个是选什么物品，一个是总重量不过界。为此我们采用二维数组，利用两个维度的索引值来解决这个问题。

假设代表重量的数组为W，代表价值的数组为P。

状态c[

i ][

j ]表示前

i 件物品在重量

j 内的最大总价值，注意这个状态不是很好理解，前

i 件物品可以选可以不选，重量

j 内说明当前状态的总重量并没有超过

j。

同样这个问题的状态转移方程也不是很好理解，对于c[

i ][

j ]，当 

j < W【i】时，这个物件装不下，此时c[

i ][

j ]  = c[

i - 1 ][

j ]

当 

j > W【i】时，这个物品能够装下，但是此时有两种情况，第一种仍然是c[

i - 1 ][

j ]（可以理解为不装这个物品），第二种情况是c[

i - 1 ][

j - W[ i ] ] + p[ i ]（装下这个物品，但是会涉及到前一个状态c[

i - 1 ][

j - W[ i ] ]，这个我暂时没办法讲的很清楚，不过这个表达式的确是这样的），此时c[

i ][

j ] 为两者中较大的那个值。

直接上代码，我直接定义了一种情况:

1 void main(){ 2  3 int weight = 120; 4     int w[6] = {
    0,40,50,70,40,20};    5     int p[6] = {
    0,10,25,40,20,10}; 6     int **c = (int**)malloc((6)*sizeof(int*)); 7     for (int i = 0; i <= 5; ++i){ 8         c[i] = (int*)malloc((weight+1)*sizeof(int)); 9     }10     int temp1 = 0;11     int temp2 = 0;12     for (int i = 0; i <= weight; ++i)13         c[0][i] = 0;14     for (int i = 1; i <= 5; ++i){15         c[i][0] = 0;16         for (int j = 1; j <= weight; ++j){17             if (w[i] > j)c[i][j] = c[i - 1][j];18             else{19                 temp1 = c[i - 1][j];20                 temp2 = c[i - 1][j - w[i]] + p[i];21                 c[i][j] = temp1 > temp2 ? temp1 : temp2;22             }23         }24     }25         26     cout << c[5][120] << endl;27 }