轉(zhuǎn)自：https://blog.csdn.net/xiajiawei0206/article/details/19933781

我寫這篇文章是因為我在偶然碰到了01背包的題目，而自己太菜，寫不出來，于是在百度上找到了怎么寫，然而在理解1維數(shù)組的算法時

出了些問題，理解不能，在百度上找答案，基本上沒一個我覺得看的特別懂的,或者是說得特別透徹的（也許是我太笨了），好不容易百度提問有人回答，還是覺得講的不透徹，

于是只好對比網(wǎng)上的其它這些文章自己研究了下，寫出這篇文章給大家參考下，為了幫助和我一樣困惑的人(也許我說得更本就不對 請指教啊)

初稿 :20140224? v 1.0

整理 :20140225? v 1.1

首先 什么是01背包問題？(可以參考下百度百科 只是我覺得百度百科對于為什么逆序這個問題解釋的不是特別清楚)

（以下題目中的內(nèi)容摘自百度百科）

/

題目

有N件物品和一個容量為V的背包。第i件物品的重量是c[i]，價值是w[i]。

求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大。

(01背包中這些物品每種都只有1個，每個物品只能裝一次)

基本思路

這是最基礎(chǔ)的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。

用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。

則其狀態(tài)轉(zhuǎn)移方程便是：f[i][v]=max{ f[i-1][v], f[i-1][v-c[i]]+w[i] }?？梢詨嚎s空間，f[v]=max{f[v],f[v-c[i]]+w[i]}

這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細(xì)解釋一下：

“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只牽扯前i-1件物品的問題。

如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][v]；如果放第i件物品，

那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，

此時能獲得的最大價值就是f [i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i] 即f[i-1][v-c[i]]+w[i]。

注意f[v]有意義當(dāng)且僅當(dāng)存在一個前i件物品的子集，其費用總和為v。所以按照這個方程遞推完畢后，

最終的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。

今天想了一下午01背包問題。。。? 以下是我自己總結(jié)出來的? 20140224

先舉個例子做個小實驗(該實驗可以證明順序推v是錯的)：

i????????? i-1???????????? i-1

原式子(二維的):? f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

現(xiàn)在要改成一維的(空間優(yōu)化):???? f[v]=max{ f[v],f[v-c[i]]+w[i] }

注意上面的狀態(tài)轉(zhuǎn)移方程兩邊的是2個狀態(tài)(左邊的是這一狀態(tài)? 右邊的是上一狀態(tài)（二維的通過i可以看出來）)

f[i][v]是由f[i-1][v-c[i]]推出來的,現(xiàn)在要把二維的改成一維的,即要推f[v],要保證f[v]由f[v-c[i]]推出來，

如果v是順序遞增的,則相當(dāng)于f[i][v]變得是由f[i][v-c[i]]推出來的,而不是由原來的f[i-1][v-c[i]]推的（到這里 也許你知道了原因 但可能和我當(dāng)初一樣沒真正弄懂 那么請繼續(xù)看完）(下一個狀態(tài)應(yīng)由上一個狀態(tài)來獲得)

------------------------------------------------------------------

這里可以舉個非常簡單的例子（我就不像某些網(wǎng)友舉列那么多數(shù)字的例子了 我搞個容易看懂的吧）的方法來證明v順序遞增是不行的

設(shè)有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ù)數(shù)沒意義）

原先的:? 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就不用看了 由此看來順序不行

=================================================================================

下面再來看看逆序的 我為了方便看 把上面的數(shù)據(jù)復(fù)制過來

設(shè)有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? --------------------------------

由此看來逆序就是正常的

網(wǎng)上的參考的一小段話：

==========================================================================

f[i][v]只與f[i-1][v]和f[i-1][v-C[i]]有關(guān)，即只和i-1時刻狀態(tài)有關(guān)，所以我們只需要用一維數(shù)組f[]來保存i-1時的狀態(tài)f[]。

假設(shè)i-1時刻的f[]為{a0，a1，a2，…，av}，難么i時刻的f[]中第v個應(yīng)該為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時刻的值。如果正序遍歷則當(dāng)求f[v]時

其前面的f[0],f[1]，…，f[v-1]都已經(jīng)改變過，里面存的都不是i-1時刻的值，這樣求f[v]時利用f[v-C[i]]必定是錯的值。最后f[V]即為最大價值

======================================================================

看到這里相信你們應(yīng)該能領(lǐng)悟8,90百分之了吧 或百分之百了吧 如果還是有些疑惑（恭喜你 你和我一樣笨- - (或者說你也很追求嚴(yán)謹(jǐn)?shù)乃季S。。。)最后看看我自己的理解）

我自己總結(jié)的方法去理解關(guān)于為什么v是逆序（結(jié)合上面那段話）：

注意了 這不僅和v的變化有關(guān)，還和i有關(guān)，因為是該狀態(tài)轉(zhuǎn)移方程是2種狀態(tài)，姑且這里用i和i-1來表示，i表示這個時刻的狀態(tài)，

而i-1表示上一時刻的狀態(tài)，比如逆序中： “

---------------------------? 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時刻的值,但我們現(xiàn)在需要的是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了)，所以推的值就是錯誤的,逆序是不行的

如果你還沒看懂 （呵呵 開玩笑的。。）就多輸入些數(shù)據(jù)分析看看吧，相信你們能理解的比我透徹.