首页 > 算法 数据结构 > 0-1背包

0-1背包

2012年4月30日 发表评论 阅读评论
文章作者: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背包的状态转移方程为


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大于第一个物体的重量,则背包最大价值便为该物体的价值。为了能单步验证每个状态的最优解,程序最后将状态转移矩阵的有效部分输出到了文件。

代码如下:

#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");
	}

}

测试用例:


10 3

3 4

4 6

5 7

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

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

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

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

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

#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]]的状态。状态转移方程为:


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

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


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,这一问题便解决了。

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

#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]均设为-∞或者一个比较大的负数来表示该状态是非法的。

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

代码如下:

#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;
		}
	}
}

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

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

0-1背包输出最优方案

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

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

代码如下:

#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/

  • archieyang

    if里好像还要判断j-weight[i]>=0

  • archieyang

    您好,
    感谢您的分享,看了这篇收获很多。
    提个小问题,最后一个输出最优方案的代码,i==0的时候应该特殊处理吧?

    • Yx.Ac

      恩,有反例吗? :-)