首页 > 算法 数据结构 > 多重背包

多重背包

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

---

前面已经回顾了01背包完全背包,本节回顾多重背包的几种实现形式,主要有以下几方面内容:

==多重背包问题定义 & 基本实现

==多重背包二进制拆分实现

==防火防盗防健忘

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

多重背包问题定义 & 基本实现

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

对于多重背包的基本实现,与完全背包是基本一样的,不同就在于物品的个数上界不再是v/c[i]而是n[i]与v/c[i]中较小的那个。状态转移方程如下


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

代码与完全背包的区别仅在内部循环上由


for(k = 1; k <= j/weight[i]; ++k)

变为


for(k = 1; k <=n[i] && k<=j/weight[i]; ++k)

当然,输入上的区别就不说了。

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

多重背包二进制拆分实现

跟完全背包一样的道理,利用二进制的思想将n[i]件物品i拆分成若干件物品,目的是在0-n[i]中的任何数字都能用这若干件物品代换,另外,超过n[i]件的策略是不允许的。

方法是将物品i分成若干件,其中每一件物品都有一个系数,这件物品的费用和价值都是原来的费用和价值乘以这个系数,使得这些系数分别为1,2,4,…,2^(k-1),n[i]-2^k+1,且k满足n[i]-2^k+1>0的最大整数。例如,n[i]=13,就将该物品拆成系数为1、2、4、6的四件物品。分成的这几件物品的系数和为n[i],表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数,均可以用若干个系数的和表示。

代码如下:测试用例见代码末的注释

#include <iostream>
using namespace std;

/* 多重背包 二进制拆分
 * Time Complexity  大于O(N*V)
 * Space Complexity O(N*V)
 * 设 V <= 200 N <= 10 ,拆分后 物品总数 < 50
 * 每件物品有 log n[i]种状态
 */

int maxV[201];
int weight[50]; /* 记录拆分后物体重量 */
int value[50];  /* 记录拆分后物体价值 */
int V, N;

void main()
{
	int i, j;
	scanf("%d %d",&V, &N);
	int weig, val, num;
	int count = 0;

	for(i = 0; i < N; ++i)
	{
		scanf("%d %d %d",&weig,&val,&num);

		for(j = 1; j <= num; j <= 1) // 二进制拆分
		{
			weight[count] = j * weig;
			value[count++] = j * val;
			num -= j;
		}
		if(num > 0)
		{
			weight[count] = num * weig;
			value[count++] = num * val;
		}
	}
	for(i = 0; i < count; ++i)  // 使用01背包
	{
		for(j = V; j >= weight[i]; --j)
		{
			int tmp = maxV[j-weight[i]] + value[i];
			maxV[j] = maxV[j] > tmp ? maxV[j] : tmp;
		}
	}
	printf("%d",maxV[V]);
}

/*
	【输入样例】
	4 20
	3     9     3
	5     9     1
	9     4     2
	8     1     3
	【输出样例】
	47
*/

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

简单背包基础总结:

回顾了3种简单背包后,有些思想慢慢体会,实践中,对于01背包和完全背包使用一维数组实现是最简便高效的,对于多重背包,最好就是输入时进行二进制拆分,然后使用01背包,这样比基本实现和在运算时再进行拆分要简捷的多。

防火防盗防健忘:

没事水一下:POJ  PKU

01背包: 321136243628

完全背包:125213842063

多重背包:10141276174223923260(完全+多重)

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

(全文完)

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

  • 在原佐为

    =。= 注释二进制拆分的那一行,是不是应该是y <<= 1。
    这样虽然结果没错,但是复杂度没降下来了啊。

  • yuchi ma

    代码都不能过编译,写博客这种心态,望改正

    • Yx.Ac

      说我态度问题,我还真不逃避;代码是编译过才发出来,如果有问题,请指正,我的问题我接着,虚心改正,先谢了!

    • yuchi ma

      0-0

    • Yx.Ac

      貌似评论系统有点问题,这条刚看到,囧啊,抱歉,多谢你 :-)

  • Moon

    当每件物品的权重C乘以物品数量上限M大于背包容量V时,做二进制拆分的上限就不是M,而是[V/C]了,如果M远大于[V/C]会浪费的。。。