知识点:01背包(多种姿势:二维实现+一维实现+滚动数组实现+背包装满+输出最优方案)

时间:2021-05-03 18:40:27

0-1背包

2012年4月30日Yx.Ac发表评论阅读评论 文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

四月份还没写,不能这么荒废了呀,赶紧水一篇吧,哈哈。前些日子回顾了DP的一些基础,就做一下整理吧,从0-1背包开始。

本节回顾0-1背包的基本模型,关于它的实现有很多种写法,这里对不同实现做个简单列举,主要是写代码练手了,主要有以下几方面内容:

==0-1背包问题定义 & 基本实现

==0-1背包使用滚动数组压缩空间

==0-1背包使用一维数组

==0-1背包恰好背满

==0-1背包输出最优方案

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

0-1背包问题定义 & 基本实现

问题:有个容量为V大小的背包,有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的物品,每种物品只有一个,想计算一下最多能放多少价值的货物。

DP的关键也是难点是找到最优子结构和重叠子问题,进而找到状态转移方程,编码就相对容易些。最优子结构保证每个状态是最优的,重叠子问题也即n状态的求法和n-1状态的求法是一样的;DP在实现上一般是根据状态转移方程自底向上的迭代求得最优解(也可以使用递归自顶向下求解)。

回到0-1背包,每个物体i,对应着两种状态:放入&不放入背包。背包的最优解是在面对每个物体时选择能够最大化背包价值的状态。0-1背包的状态转移方程为

1 f(i,v)
= max{ f(i-1,v), f(i-1,v-c[i])+w[i] }

f(i,v)表示前i个物体面对容量为v时背包的最大价值,c[i]代表物体i的cost(即重量),w[i]代表物体i的价值;如果第i个物体不放入背包,则背包的最大价值等于前i-1个物体面对容量v的最大价值;如果第i个物体选择放入,则背包的最大价值等于前i-1个物体面对容量v-cost[i]的最大价值加上物体i的价值w[i]。

对于实现,一般采用一个二维数组(状态转移矩阵)dp[i][j]来记录各个子问题的最优状态,其中dp[i][j]表示前i个物体面对容量j背包的最大价值。

下面给出0-1背包的基本实现,时间复杂度为O(N*V),空间复杂度也为O(N*V),初始化的合法状态很重要,对于第一个物体即f[0][j],如果容量j小于第一个物体(编号为0)的重量,则背包的最大价值为0,如果容量j大于第一个物体的重量,则背包最大价值便为该物体的价值。为了能单步验证每个状态的最优解,程序最后将状态转移矩阵的有效部分输出到了文件。

代码如下:

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 #include
<iostream>
using
namespace std;
 /*
0-1背包 版本1
 * Time Complexity  O(N*V) * Space Complexity O(N*V) * 设 V <= 200 N <= 10 * 状态转移方程:f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] } */ int
maxValue[11][201]; /* 前i个物体面对容量j的最大价值,即子问题最优解 */
int
weight[11];
int
value[11];
int
V, N;
 void
main()
{    int i, j;    scanf("%d %d",&V, &N);    for(i = 0; i < N; ++i)    {        scanf("%d %d",&weight[i],&value[i]);    }    for(i = 0; i < N; ++i)    {        for(j = 0; j <= V; ++j) /* 容量为V 等号 */        {            if(i > 0)            {                maxValue[i][j] = maxValue[i-1][j];                if(j >= weight[i]) /* 等号 */                {                    int tmp = maxValue[i-1][j-weight[i]] + value[i];                    maxValue[i][j] = ( tmp > maxValue[i][j]) ? tmp : maxValue[i][j];                }            }else   /* 数组第0行赋值 */            {                if(j >= weight[0])                    maxValue[0][j] = value[0];            }        }    }     printf("%d",maxValue[N-1][V]);     /* 重定向输出结果到文件 */    freopen("C:\\dp.txt","w",stdout);    for(i = 0; i <= N; ++i)    {        for(j = 0; j <= V; ++j)        {            printf("%d   ",maxValue[i][j]);        }        printf("\n");    } }

测试用例:

1234567 10
3
 3
4
 4
6
 5
7

程序输出的状态转移矩阵如下图,第一行表示第1个物体对于容量0至V时的最优解,即背包最大价值。该实现方法是0-1背包最基本的思想,追踪状态转移矩阵有助于加深理解,POJ上单纯的0-1背包题目也有不少,如3624等,可以水一下,加深理解。

知识点:01背包(多种姿势:二维实现+一维实现+滚动数组实现+背包装满+输出最优方案)

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

0-1背包使用滚动数组压缩空间

所谓滚动数组,目的在于优化空间,从上面的解法我们可以看到,状态转移矩阵使用的是一个N*V的数组,在求解的过程中,我们可以发现,当前状态只与前一状态的解有关,那么之前存储的状态信息已经无用了,可以舍弃的,我们只需要空间存储当前的状态和前一状态,所以只需使用2*V的空间,循环滚动使用,就可以达到跟N*V一样的效果。这是一个非常大的空间优化。

代码如下,我们可以在每轮内循环结束后输出当前状态的解,与上面使用二维数组输出的状态转移矩阵对比,会发现是一样的效果,重定向输出到文本有助加深理解。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 #include
<iostream>
using
namespace std;
 /*
0-1背包 版本2
 * Time Complexity  O(N*V) * Space Complexity O(2*V) * 设 V <= 200 N <= 10 * 状态转移方程:f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] } */ int
maxValue[2][201]; /* 前i个物体面对容量j的最大价值,即子问题最优解 */
int
weight[11];
int
value[11];
int
V, N;
 void
main()
{    int i, j, k;    scanf("%d %d",&V, &N);    for(i = 0; i < N; ++i)    {        scanf("%d %d",&weight[i],&value[i]);    }    for(i = 0; i < N; ++i)    {        for(j = 0; j <= V; ++j) /* 容量为V 等号 */        {            if(i > 0)            {                k = i & 1;    /* i%2 获得滚动数组当前索引 k */                 maxValue[k][j] = maxValue[k^1][j];                if(j >= weight[i]) /* 等号 */                {                    int tmp = maxValue[k^1][j-weight[i]] + value[i];                    maxValue[k][j] = ( tmp > maxValue[k][j]) ? tmp : maxValue[k][j];                }            }else   /* 数组第0行赋值 */            {                if(j >= weight[0])                    maxValue[0][j] = value[0];            }        }    }     printf("%d",maxValue[k][V]);     /* 重定向输出结果到文件 */    freopen("C:\\dp.txt","w",stdout);    for(i = 0; i <= 1; ++i)    {        for(j = 0; j <= V; ++j)        {            printf("%d ",maxValue[i][j]);        }        printf("\n");    } }

这种空间循环滚动使用的思想很有意思,类似的,大家熟悉的斐波那契数列,f(n) = f(n-1) + f(n-2),如果要求解f(1000),是不需要申请1000个大小的数组的,使用滚动数组只需申请3个空间f[3]就可以完成任务。

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

0-1背包使用一维数组

使用滚动数组将空间优化到了2*V,在背包九讲中提到了使用一维数组也可以达到同样的效果,个人认为这也是滚动思想的一种,由于使用一维数组解01背包会被多次用到,完全背包的一种优化实现方式也是使用一维数组,所以我们有必要理解这种方法。

如果只使用一维数组f[0…v],我们要达到的效果是:第i次循环结束后f[v]中所表示的就是使用二维数组时的f[i][v],即前i个物体面对容量v时的最大价值。我们知道f[v]是由两个状态得来的,f[i-1][v]和f[i-1][v-c[i]],使用一维数组时,当第i次循环之前时,f[v]实际上就是f[i-1][v],那么怎么得到第二个子问题的值呢?事实上,如果在每次循环中我们以v=v…0的顺序推f[v]时,就能保证f[v-c[i]]存储的是f[i-1][v-c[i]]的状态。状态转移方程为:

1 v
= V...0; f(v) = max{ f(v), f(v-c[i])+w[i] }

我们可以与二维数组的状态转移方程对比一下

1 f(i,v)
= max{ f(i-1,v), f(i-1,v-c[i])+w[i] }

正如我们上面所说,f[v-c[i]]就相当于原来f[i-1][v-c[i]]的状态。如果将v的循环顺序由逆序改为顺序的话,就不是01背包了,就变成完全背包了,这个后面说。这里举一个例子理解为何顺序就不是01背包了

假设有物体z容量2,价值vz很大,背包容量为5,如果v的循环顺序不是逆序,那么外层循环跑到物体z时,内循环在v=2时,物体z被放入背包,当v=4时,寻求最大价值,物体z放入背包,f[4]=max{f[4],f[2]+vz},这里毫无疑问后者最大,那么此时f[2]+vz中的f[2]已经装入了一次物体z,这样一来该物体被装入背包两次了就,不符合要求,如果逆序循环v,这一问题便解决了。

代码如下,为了加深理解,可以在内循环结束输出每一个状态的情况到文本中,会发现与使用二维数组时的状态转移矩阵都是一样一样的。

12345678910111213141516171819202122232425262728293031323334353637383940414243 #include
<iostream>
using
namespace std;
 /*
0-1背包 版本3
 * Time Complexity  O(N*V) * Space Complexity O(V) * 设 V <= 200 N <= 10 * 状态转移方程:v = V...0; f(v) = max{ f(v), f(v-c[i])+w[i] } */ int
maxV[201];    /* 记录前i个物品中容量v时的最大价值 */
int
weight[11];
int
value[11];
int
V, N;
 void
main()
{    int i, j;    scanf("%d %d",&V, &N);    for(i = 0; i < N; ++i)    {        scanf("%d %d",&weight[i],&value[i]);    }     /*     * 对于第i轮循环     * 求出了前i个物品中面对容量为v的最大价值    */    for(i = 0; i < N; ++i)    {        /*         * 内循环实际上讲maxV[0...v]滚动覆盖前一轮的maxV[0...V]         * 可输出对照使用二维数组时的情况         * j从V至0逆序是防止有的物品放入背包多次        */        for(j = V; j >= weight[i]; --j)   /* weight > j 的物品不会影响状态f[0,weight[i-1]]  */        {            int tmp = maxV[j-weight[i]]+value[i];            maxV[j] = (maxV[j] > tmp) ? maxV[j] : tmp;        }    }    printf("%d",maxV[V]);}

可以看出,使用一维数组,代码非常简练。

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

0-1背包恰好背满

在01背包中,有时问到“恰好装满背包”时的最大价值,与不要求装满背包的区别就是在初始化的时候,其实对于没有要求必须装满背包的情况下,初始化最大价值都为0,是不存在非法状态的,所有的都是合法状态,因为可以什么都不装,这个解就是0,但是如果要求恰好装满,则必须区别初始化,除了f[0]=0,其他的f[1…v]均设为-∞或者一个比较大的负数来表示该状态是非法的。

这样的初始化能够保证,如果子问题的状态是合法的(恰好装满),那么才能得到合法的状态;如果子问题状态是非法的,则当前问题的状态依然非法,即不存在恰好装满的情况。

代码如下:

123456789101112131415161718192021222324252627282930 #include
<iostream>
using
namespace std;
 int
maxV[201];    /* 记录前i个物品中容量v时的最大价值 */
int
weight[11];
int
value[11];
int
V, N;
 void
main()
{    int i, j;    scanf("%d %d",&V, &N);    for(i = 0; i < N; ++i)    {        scanf("%d %d",&weight[i],&value[i]);    }    for(i = 1; i <= V; ++i)  /* 初始化非法状态 */    {        maxV[i] = -100;    }     for(i = 0; i < N; ++i)    {        for(j = V; j >= weight[i]; --j)        {            int tmp = maxV[j-weight[i]]+value[i];            maxV[j] = (maxV[j] > tmp) ? maxV[j] : tmp;        }    }}

为了加深理解,输出每轮循环的状态矩阵如下,对照每个物体的情况,就会理解为什么做那样的初始化了。

知识点:01背包(多种姿势:二维实现+一维实现+滚动数组实现+背包装满+输出最优方案)

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

0-1背包输出最优方案

一般来讲,背包问题都是求一个最优值,但是如果要求输出得到这个最优值的方案,就可以根据状态转移方程往后推,由这一状态找到上一状态,依次向前推即可。

这样就可以有两种实现方式,一种是直接根据状态转移矩阵向前推,另一种就是使用额外一个状态矩阵记录最优方案的路径,道理都是一样的。当然也可以使用一维数组,代码更为简练,这里不罗列,相关代码可以到这里下载。

代码如下:

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 #include
<iostream>
using
namespace std;
 /*
0-1背包 输出最优方案 2 直接根据状态数组算
 * Time Complexity  O(N*V) * Space Complexity O(N*V) * 设 V <= 200 N <= 10 * 状态转移方程:f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] } */ int
maxValue[11][201]; /* 记录子问题最优解 */
int
weight[11];
int
value[11];
int
V, N;
 void
main()
{    int i, j;    scanf("%d %d",&V, &N);    for(i = 0; i < N; ++i)    {        scanf("%d %d",&weight[i],&value[i]);    }    for(i = 0; i < N; ++i)    {        for(j = 0; j <= V; ++j)        {            if(i > 0)            {                maxValue[i][j] = maxValue[i-1][j];                if(j >= weight[i])                {                    int tmp = maxValue[i-1][j-weight[i]] + value[i];                    maxValue[i][j] = ( tmp > maxValue[i][j]) ? tmp : maxValue[i][j];                }            }else            {                if(j >= weight[0])                    maxValue[0][j] = value[0];            }        }    }     printf("%d\n",maxValue[N-1][V]);     i = N-1;    j = V;    while(i >= 0)    {        if(maxValue[i][j] == maxValue[i-1][j-weight[i]] + value[i])        {            printf("%d ",i);            j = j - weight[i];        }        --i;    }}

01背包是背包问题的基础,加深理解的最好方式就是动手写一下,然后对照最终的状态转移矩阵一一比对。

本文相关代码可以到这里下载。

(全文完)

参考资料:背包问题九讲 http://love-oriented.com/pack/