算法

背包问题学习笔记(1)-基本的背包问题介绍

背包问题是动态规划中非常经典的问题。这里仅仅是一份学习笔记和简单的代码实现，更详细的介绍请见参考1和2。

01背包问题

题目

有\(N\)种物品和一个容量为\(V\)的背包，每种物品都有无限件可用。放入第i种物品的费用是\(C_i\)，价值是\(W_i\)。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

基本思路

\(F[i,v]\)代表前\(i\)件物品放入容量为\(v\)的背包可以获得的最大价值。 01背包的状态转移方程为: \[F[i,v]=\max\{F[i-1][v],F[i-1][v-C_i]+W_i\}\] 将“前\(i\)件物品放入容量为\(v\)的背包”中这个子问题，只考虑地\(i\)件物品的策略(放或不放）。如果放入\(i\)物品，问题转为“前i-1件物品放入容量为\(v-C_i\) 的背包中“这个子问题的最大价值\(F[i-1,v-C_i]\)加上\(W_i\)。如果不放，问题转化为”前i-1件物品放入容量为\(v-C_i\) 的背包中“,价值为\(F[i-1,v]\)。

代码是 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include
using namespace std;
const int N=3,V=10;//物品数目N，背包容量V
int F[N+1][V+1];//二维数组
int FOne[V+1];//一维数组
int C[N+1]={0,3,4,5};//物品容量C
int W[N+1]={0,4,6,7};//物品价值W
int max(int a,int b)
{
	if(a>=b)
		return a;
	else
		return b;
}
void BasicZeroOnePack()//O(NV)
{
	memset(F,0,sizeof(F));
	for(int i=1;i<=N;i++)
	{
		for(int v=0;v<=V;v++)
		{
			F[i][v]=F[i-1][v];//默认不加入物品，有可能物品空间太大背包放不下
			if(v>=C[i])//可以加入的时候考虑一下
				F[i][v]=max(F[i-1][v],F[i-1][v-C[i]]+W[i]);
		}
	}

注：由于后面代码有很多一样的地方，所以后面的就只列函数和不同的地方，数组定义和max函数定义什么就省略了。

空间复杂度优化———一维数组

因为状态转移方程只用到了i-1的状态，i-1之前的状态都用不上。所以只要保证我们在算\(F[i,v]\)时，能取得\(F[i-1,v]\)和\(F[i-1,v-C_i]\)的值即可。在只使用一维数组的情况下，只要保证在覆盖当前位置前，\(F[v]\)保存的是i-1时刻的\(F[v]\)的值就行，\(F[v-C_i]\)也是类似。所以只要每次循环中以\(v \leftarrow V,\ldots,0\) 的递减顺序计算更新\(F[v]\)就可以了。 关键代码如下

1
2
3
4
5
6
7
8
9
10
11
12
void ZeroOnePack()//一维数组搞定，O(N)的空间
{
	memset(FOne,0,sizeof(FOne));
	for(int i=1;i<=N;i++)
	{
		for(int v=V;v>=C[i];v--)
		{
			FOne[v]=max(FOne[v],FOne[v-C[i]]+W[i]);
			//cout<<i<<" "<<v<<" "<<F[0][v]<<endl;
		}
	}
}

事实上，由于后面的问题可以分解为一维数组解01背包问题，所以将处理01背包问题中的一个物品的过程抽象出来，定义如下。

1
2
3
def ZeroOnePack(F,C,W)
   for(v = V to C)
      F[v]=max(F[v],F[v-C]+W)

完全背包问题

题目

有N种物品和一个容量为V的背包，每种物品都有无限件可用。放入第i种物品的费用是\(C_i\)，价值是\(W_i\)。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

基本思路

如果按01背包的思路，我们只要有状态转移矩阵 \[F[i,v]=\max\{F[i-1][v-k C_i]+k W_i|0 \leq k \leq [v/C_i]\}\] 这个问题有\(O(VN)\)个状态要解，而且求每个状态的时间是\(O(\frac{v}{C_i})\)，总的复杂度上界是\(O(NV\sum \frac{V}{C_i})\)，还是比较大的。 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void BasicCompletePack()  //O(NVsum(V/C_i))的算法
{
	memset(F,0,sizeof(F));
	for(int i=1;i<=N;i++)
	{
		for(int v=1;v<=V;v++)
		{
			int max=F[i-1][v];
			int kmax=v/C[i];
			F[i][v]=F[i-1][v];  //还是默认不加入物品,这是k=0的情况
			if(kmax>=1)//v>=c[i];
			{
				for(int k=1;k<=kmax;k++)
				{
					if(F[i-1][v-k*C[i]]+k*W[i]>max)
					{
						max=F[i-1][v-k*C[i]]+k*W[i];
					}
				}
				F[i][v]=max;
			}
		}
	}
}

优化思路——————反向考虑

我们的问题是求”前\(i\)件物品放入容量为\(v\)的背包“的最大价值，原先的循环是先确定前i-1个物品的最优策略，然后考虑加不加物品\(i\)，来比较不同容量\(v\)下背包的价值是否有变化，但是这里物品\(i\)变成多个可选了，所以复杂度提高了。我们反过来想，先确定背包\(v-1\)容量时的物品的最优策略，然后考虑\(v\)容量下，对于随着可选物品\(i\)的增多，考虑背包的最大价值是否有变化。 状态转移方程为 \[F[i,v]=\max\{F[i-1][v],F[i][v-C_i]+W_i\}\] 这里\(F[i-1][v]\)是不选第\(i\)个物品时，背包的最大价值，\(F[i][v-C_i]+W_i\)是选了物品\(i\)时，背包的最大价值。需要注意的是，在\(v\)增长的过程中，物品\(i\)有可能被选择多次，因为每轮\(v\)的循环都要考虑一次物品\(i\)。 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void RerVerseCompletePack()
{
	memset(F,0,sizeof(F));
	for(int v=1;v<=V;v++)
	{
		for(int i=1;i<=N;i++)
		{
			if(v<C[i])
			{
				F[i][v]=F[i-1][v];//如果物品i放不进去，选择前i-1中最好的结果
			}
			else
			{
				F[i][v]=max(F[i-1][v],F[i][v-C[i]]+W[i]);
			}
		}
	}
}

进一步优化——————一维数组

直接先给出代码:

1
2
3
4
5
6
7
8
9
10
11
void CompletePack()  //一维数组搞定，O(N)的空间
{
	memset(FOne,0,sizeof(FOne));
	for(int i=1;i<=N;i++)
	{
		for(int v=C[i];v<=V;v++)
		{
			FOne[v]=max(FOne[v],FOne[v-C[i]]+W[i]);
		}
	}
}

这个算法的时间复杂度也是\(O(VN)\)，但空间复杂度只有\(O(N)\)。你会注意到，这个代码与01背包的优化算法只有\(v\)的循环顺序不同而已。这个不同之处就是问题的关键。在\(v \leftarrow V,\ldots,0\) 的递减顺序计算的时候，背包内除了当前加或不加的物品\(i\)以外，其余的物品一定是前\(i-1\)个之中的，这样保证了物品\(i\)只会被处理一次。而完全背包问题中，物品\(i\)是可以加无数次的，我们在对当前容量\(v\)的背包做加不加物品\(i\)的策略时，是根据有可能在之前较小的容量\(v\)中已经选入第\(i\)种物品的子结果\(F[i,v-C_i]\)中得到的（而不是\(F[i-1,C_i]\))。 所以，写出来的状态转移方程是这 \[F[v]=\max\{F[v],F[v-C_i]+W_i\}\] 我们可以理解为 \[F[i,v]=\max\{F[i-1][v],F[i][v-C_i]+W_i\}\] 和优化思路1的状态转移方程一摸一样。 同样，我们将完全背包的过程抽象出来:

1
2
3
def CompletePack(F,C,W)
   for(v = C to V)
      F[v]=max(F[v],F[v-C]+W)

多重背包问题

题目

有N种物品和一个容量为V的背包。第i种物品最多有\(M_i\)件可用，每件耗费的空间是\(C_i\)，价值是\(W_i\)。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

基本思路

基本思路和完全背包类似，就是将\(k\)的上限改为\(M_i\)即可，这里就不写了。

优化算法———转为01背包问题

如果我们直接把第\(i\)种物品的看做对\(M_i\)个01背包物品做选择的话，其复杂度其实并没有下降。

换一种拆分方式，我们希望把第\(i\)中物品换成一些小的物品，不管第\(i\) 种物品有几件，都可以由这些小物品的相互组合得到。现在考虑二进制的思想，把物品拆成\(2^k*C_i\),\(1,2,2^{k-1}\),价值为\(2^k*W_i\)的物品。假设最大物品数量是\(M_i\)，必定存在一个k,使得\(1+2+2^2+\ldots+2^{k-1} \leq M_i \leq 1+2+2^2+\ldots+2^k\)。用\(k\)位二进制最多能表示到\(\sum_{i=1}^k 2^{i-1}=2^k+1\)这么大的数，而由上面的式子，肯定有\(M_i-2^k+1<2^k\)，所以用\(k\)位二进制数就可以表示系数中的最大值\(M_i-2^k+1\)。令系数为\(1+2+2^2+\ldots+2^{k-1},M_i-2^k+1\)，\(k\)是满足\(M_i-2^k+1>0\)的最小整数。

同样地，完全背包也可以使用这个方法，只不过上限变成了\([v/C_i]\)而已。

给出代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int M[N+1]={0,2,1,1};//多了一个物品数目M的限制
int CBinary[100];//二进制拆分完的新物品容量
int WBinary[100];//二进制拆分完的新物品价值
int FOneBinary[100];//二进制拆分完的一维数组
void MultiplePack()
{memset(FOneBinary,0,sizeof(FOneBinary));
	int num=1;//记录新物品总数目
	for(int i=1;i<=N;i++)
	{
		int thisM=M[i];
		if(thisM>V/C[i])//如果太大的话
		{
			thisM=V/C[i];
		}
		for(int k=1;k<thisM;k=k*2)//0<M-2^k+1<2^(k+1)
		{
			CBinary[num]=k*C[i];
			WBinary[num]=k*W[i];
			num++;
			thisM=thisM-k;
		}
		//再加一遍
		CBinary[num]=thisM*C[i];
		WBinary[num]=thisM*W[i];
		num++;
	}
	//拆分完毕，开始01背包
	for(int i=1;i<=num;i++)
	{
		for(int v=V;v>=CBinary[i];v--)
		{
			FOneBinary[v]=max(FOneBinary[v],FOneBinary[v-CBinary[i]]+WBinary[i]);
		}
	}
}

将整个过程抽象出来,得到

1
2
3
4
5
6
7
8
9
10
def MultiplePack(F,C,W,M)
if M>=[V/C]//如果自定义的上限超过了背包可以装的量，就变成完全背包问题了，可以做二进制拆分，也可以直接用完全背包的方法做。
   CompletePack(F,C,W);
   return;
k=1;
while(k<M)
   ZeroOnePack(KC,kW);
   M=M-k;
   k=k*2;
ZeroOnePack(M*C,M*W）；//处理最后一个

多重背包衍生问题——————只求可行性的算法

问题

有N件物品和一个容量为V的背包。放入第i件物品最多有\(M_i\)件可用，每件占用的容量是\(C_i\)。求是否能刚好填满给定容量的背包。这个问题只求可行性，不考虑价值，有复杂度为\(O(VN)\)的算法。

基本思路

这个问题是有\(O(VN)\)的解法的，它的思想是这样的，令\(F[i][j]\)代表“用了前\(i\)中物品刚好填满容量为\(j\)的背包后，还留下的可用物品\(i\)的个数”。如果\(F[i][j]=-1\)说明这个状态不行，如果状态可行的话应该有\(0 \leq F[i][j]\leq M_i\)。

首先，在循环到第\(i\)个物品的时候，用前\(i-1\)个物品能够填满容量为\(j\)的背包的情况必须被记录下来，这时候只要我们不选\(i\)，就可以填满容量为\(j\)的背包了。（注意，不选\(i\)的时候\(F[i][j]=M_i\)）。当然，如果用前\(i-1\)个物品能够填满容量为\(j\)的背包，那么我们只要加上一个物品\(i\)，就可以恰好填满容量为\(j+C[i]\)的背包啦。

所以状态转移矩阵是这样的， \[F[i,j]=\max{F[i][j],F[i][j-C[i]]-1}\] 两种情况，一种情况是\(F[i,j]\)是由\(F[i][j-C[i]]\)得来，因为用了一个物品\(i\)，所以值\(为F[i][j-C[i]]-1\),另一种情况是不使用物品\(i\)，由\(F[i-1,j]\) 直接得到，这时候值为\(M_i\)。 给出代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void PossbleMutiplePack()
{
	memset(F,-1,sizeof(F));//可行状态全设为-1
	F[0][0]=0;
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<=V;j++)
		{
			if(F[i-1][j]>=0)
			{
				F[i][j]=M[i];
			}
			else
				F[i][j]=-1;
		}
		for(int j=0;j<=V-C[i];j++)
		{
			if(F[i][j]>0)
			{
				F[i][j+C[i]]=max(F[i][j+C[i]],F[i][j]-1);
			}
			
		}
	}
}

最后\(F[N][0,\ldots,V]\)就是多重背包在各个容量上是否可行的答案。

混合三种背包问题

题目

如果将前面1、2、3中的三种背包问题混合起来。也就是说，有的物品只可以取一 次（01 背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限 （多重背包）。应该怎么求解呢？

解法

直接调用之前的三个过程

1
2
3
4
5
6
7
for i=1 to N
    if(第i件物品属于01背包)
        ZeroOnePack(F,C[i],W[i]);
    else if(第i件物品属于完全背包)
        CompletePack(F,C[i],W[i]);
    else if(第i件物品属于多重背包)
        MutliplePack(F,C[i],W[i],M[i]);

参考： 1.《背包问题9讲》，https://github.com/tianyicui/pack 2.师兄的博客，http://www.ahathinking.com/archives/118.html