首页 > 代码库 > 背包问题总结一

背包问题总结一

今天做数论的题目时,遇到一道多重背包的问题。好久没做过背包了,一时有点迷糊,当时理解的也不是很透彻,果断把背包九讲重新看了一遍。这里做下总结,加深自己的理解。


背包问题求的是在花费一定代价(物品的重量或体积)下,一个背包装入物品后所获得的最大价值。总的包括三种基本的背包:01背包,完全背包,多重背包。还有由这三种背包延伸出来的问题:混合背包,二维费用的背包,分组背包,背包问题问法的变化等。


01背包是最基本的背包,有N种物品,第i件物品的花费是c[i],价值是w[i],每种物品只有一件,求将哪些物品装入背包获得的价值最大。

完全背包,有N种物品,第i件物品的花费是c[i],价值是w[i],每种物品有无限件,求将哪些物品装入背包使这些物品的费用不超过背包容量,且总价值最大。

多重背包,有N种物品,第i件物品的花费是c[i],价值是w[i],每种物品有有限件为n[i],求将哪些物品装入背包使这些物品的费用不超过背包容量,且总价值最大。

可见,三种背包的不同之处是物品的数目不一样。其实完全背包和多重背包都可以转化为01背包求解。


01背包

因为每种物品只有一件,有选和不选两种可能。设f[i][v]表示前i种物品恰好放入容量为v的背包的最大价值。那么可以得到状态转移方程f[i][v] = max(f[i-1][v], f[i-1][v-c[i]]+w[i]),即第i种物品不放为f[i-1][v],放为f[i-1][v-c[i]]+w[i],取较大值。其时间复杂度为O(nv)。

其实我们可以用一个一维数组表示上述状态的转移f[v],它与f[i][v]的意义相同。我们可以得到01背包如下:

void ZeroOnePack()
{
	for(int i = 1; i <= N; i++)
	{
		for(int v = V; v >= c[i]; v--)
			f[v] = max(f[v],f[v-c[i]]+w[i]);
	}
}
外循环很容易理解,循环N次代表N种物品,内循环是背包容量,f[v]对应f[i-1][v],f[v-c[i]]+w[i]对应f[i-1][v-c[i]]+w[i]。但注意是逆序。因为f[v]是从上一个状态推出来的,上一个状态是f[i-1][v]或f[i-1][v-c[i]]+w[i],即还没有放当前物品。如果是按顺序的话,意味着f[i][v]是由f[i][v-c[i]]推出来,显然与01背包每件物品只有一件相违背。


初始化问题:有的题目要求恰好装满背包,而有的没有要求恰好装满,它们在初始化上有细微差别。

如果要求恰好装满背包,那么f[0]初始为0,f[1...V]初始为-INF(如果求最大价值),最小价值初始为-INF,初始化就是在没有放任何物品时背包的合法状态,因为只有背包容量为0的时候,恰好有价值为0的nothing"恰好装满",它属于合法状态,其余均不是。

如果没有要求必须装满,f[0...V]初始化为0,因为任何容量的背包都有一个合法状态,就是不放入物品。

这里的初始化也适用于以下的背包问题。



完全背包

与01背包不同的是这里的每种物品都有无限件,每种物品就不是放与不放的问题了,而是放0个,1个.....v/c[i]个的问题。子状态f[i][v]定义为前i种物品恰好装入容量为v的背包的最大价值。那么状态转移方程为

f[i][v] = max{f[i-1][v-k*c[i]]+k*w[i] | 0 <= k <= v/c[i]}。

它的时间复杂度不是O(NV),而是O(V*∑(V/c[i]) )。


完全背包可以转化为01背包求解,这里有一个O(NV)的算法:

void CompletePack()
{
	for(int i = 1; i <= N; i++)
	{
		for(int v = c[i]; v <= V; v++)
			f[v] = max(f[v],f[v-c[i]]+w[i]);
	}
}

可以发现,与01背包只是内循环的顺序不同。为什么这里是顺序呢?想一想01背包之所以逆序是因为推f[v]时必须是上一个状态,即没放第i种物品的状态,它保证了每种物品要么选要么不选。而这里每种物品有无限件,当我们加入当前第i种物品进背包的时候,可能正需要已经放入第i种物品的这样一个状态f[i][v-c[i]]。所以这里是顺序。



多重背包

多重背包中的每种物品的数目有一定的界限n[i]。每种物品可以放0个,1个......n[i]个。与完全背包类似,定义子结构f[i][v]表示前i种物品恰好装入背包容量是v的最大价值。那么它的状态转移方程为:

f[i][v] = max{f[i-1][v-k*c[i]]+k*w[i] | 0 <= k <= n[i]}。

复杂度为O(V*∑n[i])。


转化为01背包求解,就是将第i种物品分成n[i]件01背包中的物品。得到了物品数是∑n[i]件的01背包。像这样:

void MultiplePack()
{
	for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= item[i].num; j++)
		{
			for(int v = V; v >= item[i].c; v--)
				f[v] = max(f[v],f[v-item[i].c]+item[i].w);
		}
	}
}

注意内两层循环不能颠倒顺序,否则就是分组背包了。其复杂度仍然是O(V*∑n[i])。


还有一种复杂度为O(V*∑(log n[i]))的算法,利用的是二进制的思想。就是将第i种物品分成若干件物品,其中每件物品都有一个系数,这件物品的费用和价值都是原来的费用和价值乘以这个系数。这些系数分别是1,2,4...2^(k-1),n[i]-2^(k)+1,其中k是满足n[i]-2^k+1>0的最大整数。例如原来n[i] = 13,那么该种物品可以拆分成4种物品,其系数分别是1,2,4,6。而且可以证明小于等于n[i]的任何数目的物品都可以由拆分后物品的和组成。这样就减低了复杂度。具体代码为:

void ZeroOnePack(int cost, int weight)
{
	for(int v = V; v >= cost; v--)
		f[v] = max(f[v],f[v-cost]+weight);
}
void CompletePack(int cost, int weight)
{
	for(int v = cost; v <= V; v++)
		f[v] = max(f[v],f[v-cost]+weight);
}

void MultiplePack()
{
	for(int i = 1; i <= N; i++)
	{
		if(num[i] * c[i] >= V)
		{
			CompletePack(c[i],w[i]); //相当于第i种物品有无限件,可以直接完全背包。
		}
		else
		{ //转化成若干个物品,进行01背包
			int k = 1;
			while(k < amount)
			{
				ZeroOnePack(k*c[i],k*w[i]);
				amount -= k;
				k = k << 1;
			}
			ZeroOnePack(amount*c[i],amount*w[i]);
		}
	}
}


多重背包问题中还有一类,给出每种物品的价值和数目,问这些物品的组合能否到达某个价值。即判断是否可达的问题。解决这个问题,经常用一个数组use[i]记录i种物品被用的次数。具体见例题判断是否可达的问题