首页 > 算法 数据结构 > 完全背包

完全背包

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

---

前面回顾了01背包,在此基础上本节回顾完全背包的几种实现形式,主要有以下几方面内容:

==完全背包问题定义 & 基本实现

==完全背包二进制拆分思想

==完全背包使用滚动数组(略)

==完全背包中的逆向思维

==完全背包使用一维数组

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

完全背包问题定义 & 基本实现

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

与01背包不同的是,完全背包每件物体可以放入无限件(只要能放的下),故对于每件物品i,相当于拆分成了v/c[i]件相同的物品,拆分之后物品i就不是放入或不放入的两种情况了,而是放入0件、放入1件、放入2件…等情况了,对于该件物品i,最大价值取放入k件的最大值,故状态转移方程为:


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

各状态的意义不再赘述,上代码,关于复杂度以及每种物品的状态数见代码注释:

#include <iostream>
using namespace std;

/* 完全背包 版本1
 * Time Complexity  大于O(N*V)
 * Space Complexity O(N*V)
 * 设 V <= 200 N <= 10
 * 状态转移方程:f(i,v) = max{ f(i-1,v-k*c[i]) + k*w[i] | 0<=k<=v/c[i]  }
 * 每件物品有v/c[i]种状态
 */

int maxV[11][201];    /* 记录子问题最优解,物品可重复 */
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)
		{
			if(i > 0)
			{
				maxV[i][j] = maxV[i-1][j];
				if(j/weight[i] >= 1)
				{
					int max_tmp = 0;
					for(k = 1; k <= j/weight[i]; ++k)
					{
						if(maxV[i-1][j-k*weight[i]] + k*value[i] > max_tmp)
						{
							max_tmp = maxV[i-1][j-k*weight[i]] + k*value[i];
						}
					}
					maxV[i][j] = maxV[i][j] > max_tmp ? maxV[i][j] : max_tmp;
				}
			}else
			{
				if(j/weight[0] >= 1)
				{
					maxV[0][j] = j/weight[0] * value[0];
				}
			}
		}
	}
	printf("%d",maxV[N-1][V]);
}

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

完全背包二进制拆分思想

这种实现方式是对完全背包的基本实现做了一个优化,叫“二进制拆分”。所谓“拆分物体”就是将一种无限件物品拆分成有效的几件物品,拆分物体的目的是通过减少物品个数来降低复杂度。

在完全背包中,每种物品i对于容量v来讲实际上相当于有v/c[i]件,故在上述的基本实现中,k就要循环测试v/c[i]次。

这里的拆分是利用了一种二进制思想:即任何数字都可以表示成若干个2^k数字的和,例如7可以用1+2+2^2表示;这很好理解,因为任何正数都可以转成二进制,二进制就是若干个“1”(2的幂数)之和。

所以不管最优策略选择几件物品i,我们都可以将物品i拆成费用为c[i]*2^k,价值为w[i]*2^k的若干件物品。这样物品的状态数就降为了log(v/c[i]),是很大的改进。

在代码实现上,与基本实现的差别很小,区别如下

/* 完全背包 版本2
 * Time Complexity  大于O(N*V)
 * Space Complexity O(N*V)
 * 设 V <= 200 N <= 10
 * 状态转移方程:f(i,v) = max{ f(i-1,v-2^k*c[i]) + 2^k*w[i] | 0<=k<=log v/c[i]  }
 * 每件物品降低为 log(v/c[i]) 种状态
 */
for(k = 1; k <= j/weight[i]; k <<= 1)
{
     if(maxV[i-1][j-k*weight[i]] + k*value[i] > max_tmp)
     {
          max_tmp = maxV[i-1][j-k*weight[i]] + k*value[i];
     }
}

对于使用滚动数组的实现,这里就不写了,跟01背包是一样的。

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

完全背包中的逆向思维

我们知道,在01背包和完全背包的实现中,都是针对每种物品进行讨论,即外循环都是for i=0…n,然后每种物品对于容量v的变化而求得最大价值;

在完全背包中,由于物品的件数无限,所以我们可以倒过来想,我们针对每个容量讨论,外循环为容量,对于每个容量j,我们求j对于所有物品能装载的最大价值,这样一来我们就能将时间复杂度降为O(N*V)了。代码如下:


#include <iostream>
using namespace std;

/* 完全背包 版本3
 * Time Complexity  O(N*V)
 * Space Complexity O(N*V)
 * 设 V <= 200 N <= 10
 */

int maxValue[201][11]; /* 记录子问题的各状态 */
int weight[11];
int value[11];
int maxV[201]; /* 记录子问题的最优解 */
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)
	{
		int i_maxV = 0;        /* 记录子问题i的最优解 */

		/* 每个容量求面对所有物体能装载的最大价值 */
		for(j = 0; j < N; ++j)
		{
			if(i >= weight[j])
			{
				int tmp = maxV[i-weight[j]] + value[j];
				maxValue[i][j] = maxV[i-1] > tmp ? maxV[i-1] : tmp;
			}else
			{
				maxValue[i][j] = maxV[i-1];
			}
			if(maxValue[i][j] > i_maxV)
			{
				i_maxV = maxValue[i][j];
			}
		}
		maxV[i] = i_maxV;
	}

	printf("%d",maxV[V]);

	/* 重定向输出结果到文件 */
	freopen("C:\\dp.txt","w",stdout);
	for(i = 0; i <= V; ++i)
	{
		for(j = 0; j < N; ++j)
		{
			printf("%d ",maxValue[i][j]);
		}
		printf("   %d\n",maxV[i]);
	}

}

同样,可以将状态转移矩阵重定向输出到文件进行对比,一看就明白了,这里就不贴图片了。

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

完全背包使用一维数组

对于01背包和完全背包,无论是空间复杂度还是时间复杂度,最优的方法还是使用一维数组进行实现。

基于01背包的分析,由于不必考虑物品的重复放入,故v的循环采用顺序即可。代码如下:

#include <iostream>
using namespace std;

/* 完全背包 版本4
 * Time Complexity  O(N*V)
 * Space Complexity O(V)
 * 设 V <= 200 N <= 10
 * 状态转移方程:v =0...V; 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]);
	}
	for(i = 0; i < N; ++i)
	{
		for(j = weight[i]; j <= V; ++j)  /* j<weight[i]的对前面的状态不会有影响 */
		{
			int tmp = maxV[j-weight[i]]+value[i];
			maxV[j] = (maxV[j] > tmp) ? maxV[j] : tmp;
		}
	}
	printf("%d",maxV[V]);
}

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

PS:值得一提的是,在01背包和完全背包中,我们用到了两种思想,个人认为还是很有用的,其他地方也会用到很多,我们有必要在此留心:

  • 滚动数组压缩空间的思想
  • 二进制拆分的思想

记得有一回看到的面试题就用到了二进制拆分的思想,具体是啥忘了,以后碰到再说吧,就这样。

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

(全文完)

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

  • 风之谷

    完全背包二进制拆分思想,这里讲解的确实不对哦,应该是二进制拆分后,用0/1背包来做,楼主的方法二和方法一混淆在了一起了。

    • sdadasd

      那不就是01背包吗? 不过少写了一段代码吧, 6的话,应该是1,2,3,LZ代码只有1,2情况,没有剩下的3

  • Moon

    师兄加班辛苦啦~。不过真的好像不对。。。完全背包的二进制拆分应该是和多重背包是一样的,只不过物品数量上限变成了V/C[i]而不是自定义的上限。

  • Moon

    完全背包的二进制拆分部分不太明白,为什么不是像多重背包那样拆分成多个物品,之后用01背包的方法做?这里好像比较了费用为2^k的那些物品。

    • Yx.Ac

      @Moon 我很纳闷,为什么你的评论不需要我批准就能显示,,擦,我要屏蔽你,哈;不明白再好好看看吧;;咳咳,俺加班捏~~