昨天学了一整天，所以也就在精神恍惚的情况下做着低效率的事情，一个01背包搞了近乎整个白天，所以现在再次仔细分析一下01背包问题。
再次列出DP问题的套路总结
1.刻画最优解的结构特征（大概就是找出子问题解）
2.递归的定义最优解的值（写出递归式）
3.计算出问题的解，一般采取自底向上方法（填表）
4.利用计算出的信息构造一个最优解（输出路径）

开始考虑01背包问题
这里存在物品1…n（重量和价值），还有一个背包承重W（重量可以全部替换为空间）。
回想一下矩阵链乘问题，问题的最优解结构为假设将分割点设在Ak，可以获得最少的计算次数，那么由A0-Ak之间再次找到一个k使得，A0-Ak中有最好的分割方案。

1、01背包问题的最优解为考虑第i个物品能拿还是不能拿，如果能拿，那么在W – Wi的承重里，期望得到最大的价值。
2、由此,需要创建一个二维的数组，一个为0 – n 的来表示物品，一个是0 – W的来表示不同容量，g[i][j]表示在背包为j的情况下前i个物品获得最大的价值
　　　　　　「　0　　　　　　　　　　　　　i= 0 || j = 0
　　g[i][j]=　|　g[i　-　1][j]　　　　　　　　　　j< w[i]
　　　　　　Lg[i　-　1][j　–　w[i]]　+　v[i]　　j>=w[i]
由此，上面的式子还是容易理解的，把i = 0 || j = 0的部分置0，没有物品可拿和空间没有都置为0，如果背包容得下当前的内容，那么，在这件物品给其他物品剩余的空间里获得最大价值加上拿上这件物品的价值就是最大的价值。
再次对比一下矩阵链乘，矩阵链乘考虑的是在g[i][j]为Ai – Aj 的范围内获得的最大价值，所以当i == j 的情况下应当全部置0，之后考虑为 1-2、1-3、1-4、…、1-n，2-3、2-4、2-5、…、2-n，所以后来有了那个金字塔般的图。计算的方法为左边和右边次数加上左右相乘需要的次数。
3.填表的思路已经非常明确了，i层为物品，j层为背包承重，i层来做外层循环，填完表之后，大的数据会沉到最后一行，在最后一行当中找到最大的值就可输出了
4.在路径输出的方法上，我也花了很多时间，我多用了一个表示在和不在的空间来寻找如果在输出，之后j减去物品重量，i – 1，如果不在，i直接- 1，这个过程通过想象拿物品的过程很好理解。不过昨天一整天坐在电脑前实在是效率低下。

最后贴上代码吧，还是要多学习其他大神的代码，我的程序总是显得较为臃肿，当然啦，现在不是需要程序写的思路清晰嘛，希望我的程序让人看起来能够更好的理解。
#include<stdio.h>
#define　NUM　120
enum　Status{
　　IN,OUT
};
struct　treasure{
　　int　weight;
　　int　value;
};
void　PrintPath(enum　Status　flag[NUM][NUM],struct　treasure　trea[NUM],int　graph[NUM][NUM] , int　num , int　bagWeight)
{
　　int　i　=　num;//物品数目
　　int　j　=　bagWeight;
　　int　max　=　0;
//找到最大价值
　　while(j　>　0)
　　{
　　　　if(graph[num][max] < graph[num][j])
　　　　　max= j;
　　　　j--;
　　}
　　printf("the　max　is　%d\n",graph[num][max]);
　　j　=　max;
　　while(i> 0)
　　{
　　　if(flag[i][j] == IN)
　　　{
　　　　j-= trea[i].weight;
　　　　printf("theNO.%d is in\n",i);
　　　}
　　　--i;
　　}
}
void　Start(struct　treasure　trea[NUM],int　num)
{
　　int　bagWeight;
　　int　i,j,max;
　　int　graph[NUM][NUM];
　　enum　Status　graph_stat[NUM][NUM];
　　printf("plsinput the bag weight\n");
　　scanf("%d",&bagWeight);
　　for(i　=　0;i　<=　num;++ i)
　　　for(j　=　0;j　<=　bagWeight;++ j)
　　　　　graph_stat[i][j]= OUT;
　　for(i　=　0;i　<=　num;++i)
　　　graph[i][0]= 0;
　　for(i　=　0;i　<=　bagWeight;++ i)
　　　graph[0][i]= 0;
　　for(i　=　1;i　<=　num; ++i) //treasure
　　{
　　　for(j　=　1;j　<=　bagWeight; ++j) //bag
　　　　{
　　　　　if((trea[i].weight　<=　j)&&(graph[i-1][j]　<=　graph[i-1][j -trea[i].weight]　+　trea[i].value))
　　　　　{
　　　　　　graph[i][j]= graph[i　-　1][j　-　trea[i].weight]　+　trea[i].value;
　　　　　　graph_stat[i][j]= IN;
　　　　　}
　　　　　else
　　　　　{
　　　　　　graph[i][j]= graph[i-1][j];
　　　　　　graph_stat[i][j]= OUT;
　　　　　}
　　　　}
　　　}
　　PrintPath(graph_stat,trea,graph,num,bagWeight);
}
int　main()
{
　　　int　n　=　0;
　　　struct　treasure trearr[NUM];
　　　printf("pls　input　the　weight　and　value　until　all　the　content　in\n");
　　　for(n = 1;scanf("%d%d",&trearr[n].weight,&trearr[n].value)　!=　EOF;++　n);
　　　Start(trearr,--n);
　　　return　0;
}

靠，竟然还没有恢复，这个效率太低了吧