背包问题是一个经典的动态规划模型，容易描述，容易理解。背包问题可简单描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。01背包问题的特点是，每种物品仅有一件，可以选择放或不放。

01背包问题描述：

　　有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

写出状态转移方程：

　　f[i][v]=max{f[i-1][v], f[i-1][v-c[i]]+w[i]}

f[i][v]:  前i件物品恰放入一个容量为v的背包可以获得的最大价值

f[i-1][v]:  前i-1件物品……（同上），即不放入第i件物品的情况

f[i-1][v-c[i]]+w[i]:  放入第i件物品的情况，放入后的 f[i][v] 应该等于前 i-1 件物品在容量为 v-c[i] 上的最大价值加上 w[i]

空间优化：

　　f[i][v]=max{f[i-1][v], f[i-1][v-c[i]]+w[i]}

　　观察黑色字体部分，发现二维数组完全可以用一维数组替代：

　　f[v]=max{f[v], f[v-c[i]]+w[i]}

程序怎么写？循环如何写？

　　首先考虑如果所有的物品都能放进去，那一定就是最大价值，如果只能放进去 i （i<N）件物品，那一定要选择一个最优策略，这个策略的结果是价值最大，而每个 i 的最优策略实际上又是基于 i-1 的最优策略的。根据分析写出如下循环

　　for(i=0; i<N; ++i)

　　　　for(v=V; v>w[i]; --v)  //逆序推能够保证 f[v-c[i]] 保存的是状态是 f[i-1][v-c[i]] ，也就是每个物品只被使用了一次；顺序的话 f[v-c[i]] 保存的是 f[i][v-c[i]] ，每个物品有可能被使用多次，也就是完全背包问题的解法。

　　　　　　f[v]=max(f[v], f[v-c[i]]+w[i])

poj上的3264题就是一道简单的01背包问题，

我的代码如下：

1 #include 
      
        2 #define max(x, y) ((x)>(y) ? (x) : (y)) 3 int w[3403]; 4 int d[3403]; 5 int f[13000]; 6 int main() 7 { 8     int i, j, n, m; 9     int nMax = 0;10     scanf("%d %d", &n, &m);11     for(i=0; i
       
        =w[i]; --j)18         {19             //printf("%d %d %d %d %d %d %d\n", __LINE__, j, i, f[j], w[i], d[i], f[j-w[i]]+d[i]);20             f[j] = max(f[j], f[j-w[i]]+d[i]);21         }22     }23     printf("%d\n", f[m]);24     return 0;25 }
       
      

poj上1384是一道完全背包问题，不过该问题求解的最小值，跟求最大值的最主要区别是小心初始化状态数组。

这里也给出代码：

1 #include 
      
        2 #define min(x, y) ((x)<(y) ? (x) : (y)) 3 #define MAX_INT 10000000   4 int p[501]; 5 int w[501]; 6 int f[10001]; 7 int main() 8 { 9     int t;10     scanf("%d", &t);11     while(t--)12     {13         int i, j, E, F, n, W;14         for(i=0; i<10001; ++i)15         {16             f[i] = MAX_INT;//注意初始化17         }18         f[0] = 0; //注意初始化19         scanf("%d %d", &E, &F);20         scanf("%d", &n);21         W = F-E;22         for(i=0; i