动态规划入门三---背包问题（1）
序言背包问题是最广为人知的动态规划问题之一，拥有很多的变形，尽管在理解之后不难写出程序，但是往往要花费一定的时间真正的掌握它。
多阶段决策问题1引例 物品无限的背包问题有n种物品，每种均为无穷多个。第i个物品的体积为Vi,重量为Wi。选一些物品装入一个容量为C的背包，是的背包内的物品在总体积不超过C的情况下重量尽可能地大。1<= n<= 100, 1<=C<=10000, 1<= Wi <= 1000000
【分析】似乎很眼熟，因为这个就是之前的DAG的硬币问题扩展版，不过增加了一个属性重量。即是原来的无权图便成了有权图。问题便成了求以C为起点的（终点任意）的，边权之和最大的路径。此时最大的变化就是把原来的+1，变成了 + W[ i ] 。
2 0--1背包问题有n种物品，每种只有一个。第i个物品的体积为Vi，重量为Wi。选一些物品装入一个容量为C的背包，是的背包内的物品在总体积不超过C的情况下重量尽可能地大。1<= n<= 100, 1<=C<=10000, 1<= Wi <= 1000000 。
【分析】此时可以发现，原来的只靠“剩余体积”这个状态，无法再做此题，因为不知道每个物品是否已经被用过。也即是原来的状态转移太过混乱，任何时候均可以使用任何物品，所以，我们要把决策有序化！
【解决思想】
引入阶段的概念，具体参见回溯法的理解。
【算法设计】用d(i，j) 表示当前在第i层，背包剩余剩余容量为j时候接下来的最大重量和，则就分为两种情况：第一种是把第j个物品放进去，此时背包的重量是d(i+1,j -V[ i ] ) + W[ i ] ,第二种是不放第j个，此时背包的重量是：d（i+1，j）。所以就有了下面的式子：d(i，j) = max { d( i+1，j) ，d(i+1,j -V[ i ] ) + W[ i ] }
注意：这个递推的边界处理。下面的代码里面有提及。
提示：多阶段决策的最优化问题往往可以用动态规划来解决，其中，状态及其转移类似于回溯法的解答树。解答树中的“层数”，即是递归函数里面的“当前填充位置”，描述的是即将完成的决策序号，在DP中被称为阶段。。。
其实：说的白一点，所谓的d(i，j)代表的就是把第i个以及其后的n-i+1个物品装到容量为j的背包中的最大重量。
【算法程序代码】
第一个方法：递推法关键代码如下：

问题求助
下面代码的注释部分，觉得算法没有问题，为何就是结果不对呢？
/***** 背包问题 ********//******** written by C_Shit_Hu ************/////////////////动态规划////////////////****************************************************************************//* 有n种物品，每种只有一个。第i个物品的体积为Vi，重量为Wi。选一些物品装入一个容量为C的背包，是的背包内的物品在总体积不超过C的情况下重量尽可能地大。1<= n<= 100,  1<=C<=10000, 1<= Wi <= 1000000 。*//****************************************************************************/// 三种算法#include <stdio.h>#include <string.h>#define MAX 100int V[MAX] , W[MAX], d[MAX][MAX], f[MAX][MAX], h[MAX], WEI[MAX] ;int n, i, j, c, v, wei, ele; int max(int x,int y){return x>y ? x:y;}int main(){// 基本信息的输入printf("请输入您的背包的容积:");scanf("%d", &c);printf("请输入您要装入背包的物品种类数目:");scanf("%d", &n);// 第一种第二种需要的数据printf("请输入每种物品的体积(以空格隔开)：");for (i=0; i<n; i++)scanf("%d", &V[i]);printf("请输入每种物品的重量(以空格隔开)：");for (i=0; i<n; i++)scanf("%d", &W[i]);/*   for (i=0; i<n; i++)printf("%d  ", V[i]);for (i=0; i<n; i++)        printf("%d ",W[i]);// 第一种解决方案：递推思想解决,答案是d[1][c]for (i=n; i>=1; i--)for (j=0; j<=c; j++){d[i][j] = (i==n ? 0 : d[i+1][j] );if (j >= V[i])if(d[i][j] < (d[i+1][j-V[i]] + W[i]))d[i][j] = ( d[i+1][j-V[i]] + W[i]);}for (i=n; i>=1; i--)for (j=0; j<=c; j++)printf("%d  ",d[i][j] );printf("\n\n第一种的计算结果是：%d\n\n", d[1][c]);*/// 改变方向/* 原理介绍另外一种对称的状态定义:用f(i,j)表示“把前i个物品装入容量为j的背包中的最大重量和”，由此也可得其状态转移方程：f(i,j) == max ( f(i-1), f(i-1,j-V[i]) + W[i] )    // 同样是分为装或不装第i个边界是类似的：i=0时为0，j<0时为负无穷，最终答案是f(n, c).*/// 代码如下：for(i=0;i<=n;i++)    {        for(j=c;j>=V[i];j--)        {            WEI[j]=max(WEI[j],WEI[j-V[i]]+ W[i]);        }    }    printf("第一种的计算结果是：%d\n\n", WEI[c]);printf("请输入%d个物品的体积和重量:",n) ;for (i=1; i<=n; i ++){scanf("%d%d", &v, &wei) ; // 此处就是两种方法的区别：新的状态定义f(i,j)允许我们边读入边计算，而不必把数值存入数组for (j=0; j<=c; j++){f[i][j] = (i==1 ? 0 : f[i-1][j] );if (j >= v)if(f[i][j] <= f[i-1][j-v] + wei)f[i][j] = (f[i-1][j-v] + wei);}}printf("第二种的计算结果是：%d\n\n", f[n][c]);/*//滚动数组方式// 代码如下：memset(h, 0, sizeof(h)) ;printf("请输入%d个物品的体积和重量:", n);for(i=1; i<=n; i++){scanf("%d%d", &v, &wei) ; for(j=c; j>=0; j--)if(j>=v)if (h[j] >= h[j-v]+wei)h[j] = h[j-v] + wei;}printf("第三种的计算结果是：%d\n", h[c]);  return 0 ;*/}/******************************************************//********************  心得体会  **********************//**//******************************************************/

下一步。。。经典背包问题九讲的学习。
【未完待续……】