前言：本人是c语言初学者,能力有限，如果你比较强了，请忽略本文章。。，如果你能多给些指导,那更好啦.我写这篇文章是因为我在偶然碰到了01背包的题目，而自己太菜，
前言：本人是c语言初学者,能力有限，如果你比较强了，请忽略本文章。。，如果你能多给些指导,那更好啦.
我写这篇文章是因为我在偶然碰到了01背包的题目，而自己太菜，写不出来，于是在百度上找到了怎么写，然而在理解1维数组的算法时
出了些问题，理解不能，在百度上找答案，基本上没一个我觉得看的特别懂的,或者是说得特别透彻的（也许是我太笨了），好不容易百度提问有人回答，还是觉得讲的不透彻，
于是只好对比网上的其它这些文章自己研究了下，写出这篇文章给大家参考下，为了帮助和我一样困惑的人(也许我说得更本就不对 请指教啊)
初稿 :20140224 v 1.0
整理 :20140225 v 1.1
首先 什么是01背包问题？(可以参考下百度百科 只是我觉得百度百科对于为什么逆序这个问题解释的不是特别清楚)
（以下题目中的内容摘自百度百科）
/////////////////////////////////////////////////////////////////////////////////////
题目
有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。
求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
(01背包中这些物品每种都只有1个，每个物品只能装一次)
基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是：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件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。
如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，
那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，
此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i] 即f[i-1][v-c[i]]+w[i]。
注意f[v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，
最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。
////////////////////////////////////////////////////////////////////////////////
今天想了一下午01背包问题。。。 以下是我自己总结出来的 20140224
先举个例子做个小实验(该实验可以证明顺序推v是错的)：
i i-1 i-1
原式子(二维的): 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] }
注意上面的状态转移方程两边的是2个状态(左边的是这一状态 右边的是上一状态（二维的通过i可以看出来）)
f[i][v]是由f[i-1][v-c[i]]推出来的,现在要把二维的改成一维的,即要推f[v],要保证f[v]由f[v-c[i]]推出来，
如果v是顺序递增的,则相当于f[i][v]变得是由f[i][v-c[i]]推出来的,而不是由原来的f[i-1][v-c[i]]推的（到这里 也许你知道了原因 但可能和我当初一样没真正弄懂 那么请继续看完）(下一个状态应由上一个状态来获得)
------------------------------------------------------------------
这里可以举个非常简单的例子（我就不像某些网友举列那么多数字的例子了 我搞个容易看懂的吧）的方法来证明v顺序递增是不行的
设有3件物品 ,背包能容纳的总重量为10
i=1,2,3
物品号 重量(c) 价值(w)
i=1 4 5
i=2 7 9
i=3 5 6
f[v]=max{ f[v],f[v-c[i]]+w[i] }
如果v是顺序递增 i=1时，v=4~10 （因为v要至少大于等于c[i]嘛 不然减出个负数没意义）
原先的: f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=0 f[5]=0 f[6]=0 f[7]=0 f[8]=0 f[9]=0 f[10]=0
--------------------------- i=1 -------------------------------- 后来的： f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=5 f[5]=5 f[6]=5 f[7]=5 f[8]=0 f[9]=0 f[10]=0
v=4:
f[4]=max{f[4],f[0]+5} max{0,5}=5 f[4]=5
v=5:
f[5]=max{f[5],f[1]+5} max{0,5}=5 f[5]=5
v=6:
f[6]=max{f[6],f[2]+5} max{0,5}=5 f[6]=5
v=7:
f[7]=max{f[7],f[3]+5} max{0,5}=5 f[7]=5
v=8:
f[8]=max{f[8],f[4]+5} max{0,10}=10 f[8]=10 (这里显然不对,这时i=1，只能放一件物品,然而没有一个物品的价值为10的 )
v=9:
f[9]=max{f[9],f[5]+5} max(0,10}=10 f[9]=10
v=10:
f[10]=max{f[10],f[6]+5} max{0,10}=10 f[10]=10
--------------------------- i=1 --------------------------------
既然顺序 i=1都不对 i=2和3就不用看了 由此看来顺序不行
=================================================================================
下面再来看看逆序的 我为了方便看 把上面的数据复制过来
设有3件物品 ,背包能容纳的总重量为10
i=1,2,3
物品号 重量(c) 价值(w)
i=1 4 5
i=2 7 9
i=3 5 6
f[v]=max{ f[v],f[v-c[i]]+w[i] }
如果v是逆序,v=10~4
--------------------------- i=1 -------------------------------- f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=5 f[5]=5 f[6]=5 f[7]=5 f[8]=5 f[9]=5 f[10]=5
v=10:
max{f[10],f[6]+5} max{0,5}=5 f[10]=5
v=9:
max{f[9],f[5]+5} max{0,5}=5 f[9]=5
v=8:
max{f[8],f[4]+5} max{0,5}=5 f[8]=5
v=7:
max{f[7],f[3]+5} max={0,5}=5 f[7]=5
v=6:
max{f[6],f[2]+5} max={0,5}=5 f[6]=5
v=5:
max{f[5],f[1]+5} max={0,5}=5 f[5]=5
v=4:
max{f[4],f[0]+5} max={0,5}=5 f[4]=5
--------------------------- i=1 --------------------------------
///////////////////////////////////////////////////////////
--------------------------- i=2 -------------------------------- f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=5 f[5]=5 f[6]=5 f[7]=9 f[8]=9 f[9]=9 f[10]=9
v=10:
max{f[10],f[3]+9} max{5,9}=9 f[10]=9
v=9:
max{f[9],f[2]+9} max{5,9}=9 f[9]=9
v=8:
max{f[8],f[1]+9} max{5,9}=9 f[8]=9
v=7:
max{f[7],f[0]+9} max{5,9}=9 f[7]=9
--------------------------- i=2 --------------------------------
///////////////////////////////////////////////////////////
--------------------------- i=3 -------------------------------- f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=5 f[5]=5 f[6]=5 f[7]=9 f[8]=9 f[9]=9 f[10]=9
v=10:
max{f[10],f[5]+6} max{9,11}=11 f[10]=11
v=9:
max{f[9],f[4]+6} max{9,11}=11 f[9]=11
v=8:
max{f[8],f[3]+6} max{9,6}=9 f[8]=9
v=7:
max{f[7],f[2]+6} max{9,6}=9 f[7]=9
v=6:
max{f[6],f[1]+6} max{5,6}=6 f[6]=6
v=5:
max{f[5],f[0]+6} max{5,6}=6 f[5]=6
--------------------------- i=3 --------------------------------
由此看来逆序就是正常的
网上的参考的一小段话：
==========================================================================
f[i][v]只与f[i-1][v]和f[i-1][v-C[i]]有关，即只和i-1时刻状态有关，所以我们只需要用一维数组f[]来保存i-1时的状态f[]。
假设i-1时刻的f[]为{a0，a1，a2，…，av}，难么i时刻的f[]中第v个应该为max(av,av-C[i]+W[i])即max(f[v],f[v-C[i]]+W[i])，
这就需要我们遍历V时逆序遍历，这样才能保证求i时刻f[v]时f[v-C[i]]是i-1时刻的值。如果正序遍历则当求f[v]时
其前面的f[0],f[1]，…，f[v-1]都已经改变过，里面存的都不是i-1时刻的值，这样求f[v]时利用f[v-C[i]]必定是错的值。最后f[V]即为最大价值
======================================================================
看到这里相信你们应该能领悟8,90百分之了吧 或百分之百了吧 如果还是有些疑惑（恭喜你 你和我一样笨- - (或者说你也很追求严谨的思维。。。)最后看看我自己的理解）
我自己总结的方法去理解关于为什么v是逆序（结合上面那段话）：
注意了 这不仅和v的变化有关，还和i有关，因为是该状态转移方程是2种状态，姑且这里用i和i-1来表示，i表示这个时刻的状态，
而i-1表示上一时刻的状态，比如逆序中： “
--------------------------- i=1 -------------------------------- f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=5 f[5]=5 f[6]=5 f[7]=5 f[8]=5 f[9]=5 f[10]=5
v=10:
max{f[10],f[6]+5} max{0,5}=5 f[10]=5
v=9:
max{f[9],f[5]+5} max{0,5}=5 f[9]=5
”
f[v]=max(f[v],f[v-C[i]]+W[i])
因为逆序遍历v中 "f[v]=max(f[v],f[v-C[i]]+W[i])"等式右边的f[v-c[i]]中的v-c[i]中的c[i]之前肯定没变过，要改变也是在求该等式左边的f[v]的后面才变，
而顺序中遍历v中,由于v是从小到大，在求等式左边的f[v]前,某个f[k](k即f[k]不是i-1时刻的值,而是i时刻的值,但我们现在需要的是i-1时刻的值来求出i时刻的值,所以通过f[v-c[i]]求出的f[v]值就是错误的值,与本题意不符合
比如："
如果v是顺序递增 i=1时,v=4~10
--------------------------- i=1 -------------------------------- f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=5 f[5]=5 f[6]=5 f[7]=5 f[8]=0 f[9]=0 f[10]=0
v=4:
f[4]=max{f[4],f[0]+5} max{0,5}=5 f[4]=5
v=5:
f[5]=max{f[5],f[1]+5} max{0,5}=5 f[5]=5
v=6:
f[6]=max{f[6],f[2]+5} max{0,5}=5 f[6]=5
v=7:
f[7]=max{f[7],f[3]+5} max{0,5}=5 f[7]=5
v=8:
f[8]=max{f[8],f[4]+5} max{0,10}=10 f[8]=10 (这里显然不对,这时i=1，只能放一件物品,然而没有一个物品的价值为10 )"
大家注意最后一行 推f[8]时用的是f[4]+5推的，而f[4]之前改变过(f[4]以变成5不是原来的0了)，所以推的值就是错误的,逆序是不行的
如果你还没看懂 （呵呵 开玩笑的。。）就多输入些数据分析看看吧，相信你们能理解的比我透彻.
京公网安备 11010802041100号