01背包问题 总结关于为什么优化成1维数组后,内层循环是逆序的?

转自:https://blog.csdn.net/xiajiawei0206/article/details/19933781

我写这篇文章是因为我在偶然碰到了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了),所以推的值就是错误的,逆序是不行的

如果你还没看懂 (呵呵 开玩笑的。。)就多输入些数据分析看看吧,相信你们能理解的比我透彻.

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,837评论 6 496
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,551评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,417评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,448评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,524评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,554评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,569评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,316评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,766评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,077评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,240评论 1 343
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,912评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,560评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,176评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,425评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,114评论 2 366
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,114评论 2 352