背包问题总结一

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

背包问题求的是在花费一定代价(物品的重量或体积)下，一个背包装入物品后所获得的最大价值。总的包括三种基本的背包：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]);
	}
}

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

如果要求恰好装满背包，那么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]);
	}
}

多重背包

多重背包中的每种物品的数目有一定的界限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]);
		}
	}
}

背包问题总结一,布布扣,bubuko.com

背包问题总结一

原文：http://blog.csdn.net/u013081425/article/details/38143705