多重背包的二進制分解思想

在背包九講裡面将多重背包轉化為01背包，并且進行時間優化，有利用到一個二進制分解的思想。

下面是在網上搜尋之後得到的一個關于二進制分解思想的講解和實作

多重背包二進制分解思想講解

/**
    在這之前，我空間好像轉過一個背包九講，現在我就隻對
    01背包和多重背包有點印象了

    先說下 01 背包，有n 種不同的物品，每個物品有兩個屬性
    size 體積，value 價值，現在給一個容量為 w 的背包，問
    最多可帶走多少價值的物品。

    int f[w+1];   //f[x] 表示背包容量為x 時的最大價值
    for (int i=0; i<n; i++)
        for (int j=w; j>=size[i]; j++)
            f[j] = max(f[j], f[j-size[i]]+value[i]);

    如果物品不計件數，就是每個物品不隻一件的話，稍微改下即可
    for (int i=0; i<n; i++)
        for (int j=size[i]; j<=w; j++)
            f[j] = max(f[j], f[j-size[i]]+value[i]);

    f[w] 即為所求

    初始化分兩種情況
    1、如果背包要求正好裝滿則初始化 f[0] = 0, f[1~w] = -INF;
    2、如果不需要正好裝滿 f[0~v] = 0;

    多重背包問題要求很簡單，就是每件物品給出确定的件數，求
    可得到的最大價值

    多重背包轉換成 01 背包問題就是多了個初始化，把它的件數C 用
    分解成若幹個件數的集合，這裡面數字可以組合成任意小于等于C
    的件數，而且不會重複，之是以叫二進制分解，是因為這樣分解可
    以用數字的二進制形式來解釋
    比如：7的二進制 7 = 111 它可以分解成 001 010 100 這三個數可以
    組合成任意小于等于7 的數，而且每種組合都會得到不同的數
    15 = 1111 可分解成 0001  0010  0100  1000 四個數字
    如果13 = 1101 則分解為 0001 0010 0100 0110 前三個數字可以組合成
    7以内任意一個數，加上 0110 = 6 可以組合成任意一個大于6 小于13
    的數，雖然有重複但總是能把 13 以内所有的數都考慮到了，基于這種
    思想去把多件物品轉換為，多種一件物品，就可用01 背包求解了。


    看代碼：
    int n;  //輸入有多少種物品
    int c;  //每種物品有多少件
    int v;  //每種物品的價值
    int s;  //每種物品的尺寸
    int count = 0; //分解後可得到多少種物品
    int value[MAX]; //用來儲存分解後的物品價值
    int size[MAX];  //用來儲存分解後物品體積

    scanf("%d", &n);    //先輸入有多少種物品，接下來對每種物品進行分解

    while (n--) {   //接下來輸入n中這個物品
        scanf("%d%d%d", &c, &s, &v);  //輸入每種物品的數目和價值
        for (int k=1; k<=c; k<<=1) { //<<右移 相當于乘二
            value[count] = k*v;
            size[count++] = k*s;
            c -= k;
        }
        if (c > 0) {
            value[count] = c*v;
            size[count++] = c*s;
        }
    }

    現在用count 代替 n 就和01 背包問題完全一樣了           

下面是利用上面的講解，對 HDOJ 2191進行解答，代碼如下:

#include <iostream>
using namespace std;

int main()
{
	int nCase,Limit,nKind,i,j,k,
		v[111],w[111],c[111],dp[111];
	//v[]存價值，w[]存尺寸，c[]存件數
	//在本題中，價值是米的重量，尺寸是米的價格

	int count,Value[1111],size[1111];
	//count存儲分解完後的物品總數
	//Value存儲分解完後每件物品的價值
	//size存儲分解完後每件物品的尺寸

	cin>>nCase;
	while(nCase--)
	{	
		count=0;
		cin>>Limit>>nKind;
		for(i=0;i<nKind;i++)
		{
			cin>>w[i]>>v[i]>>c[i];
			
			//對該種類的c[i]件物品進行二進制分解
			for(j=1;j<=c[i];j<<=1)
			{
				//<<右移1位，相當于乘2
				Value[count]=j*v[i];
				size[count++]=j*w[i];
				c[i] -= j;
			}
			if(c[i] > 0)
			{
				Value[count]=c[i]*v[i];
				size[count++]=c[i]*w[i];
			}
		}

		//經過上面對每一種物品的分解，
		//現在Value[]存的就是分解後的物品價值
		//size[]存的就是分解後的物品尺寸
		//count就相當于原來的n

		//下面就直接用01背包算法來解
		memset(dp,0,sizeof(dp));

		for(i=0;i<count;i++)
			for(j=Limit;j>=size[i];j--)
				if(dp[j] < dp[j-size[i]] + Value[i])
					dp[j]=dp[j-size[i]]+Value[i];
		
		cout<<dp[Limit]<<endl;
	}
	return 0;
}           

在背包九講裡面，他的實作方法和這個是不一樣的，他是利用01背包和完全背包來配合實作的，下面是那個版本的實作

/*
HDOJ 2191
多重背包用二進制轉化的思想，進行優化
*/

#include <iostream>
using namespace std;

int weight[110],Value[110],num[110];
int f[1100];
int limit;

inline void ZeroOnePack(int w,int v)
{
	int j;
	for(j=limit;j>=w;j--)
	{
		if(f[j-w]+v > f[j])
			f[j]=f[j-w]+v;
	}
}

inline void CompletePack(int w,int v)
{
	int j;
	for(j=w;j<=limit;j++)
	{
		if(f[j-w]+v > f[j])
			f[j]=f[j-w]+v;
	}
}

inline void MultiplePack(int w,int v,int amount)
{
	if(amount * w >= limit)
	{
		CompletePack(w,v);
		return ;
	}
	for(int k=1;k<amount;k<<=1)
	{
		ZeroOnePack(k*w,k*v);
		amount -= k;
	}
	ZeroOnePack(amount*w,amount*v);
}

int main()
{
	int T,n;
	cin>>T;
	while(T--)
	{
		cin>>limit>>n;
		
		for(int i=0;i<n;i++)
			cin>>weight[i]>>Value[i]>>num[i];
		
		memset(f,0,sizeof(f));
		
		for(i=0;i<n;i++)
			MultiplePack(weight[i],Value[i],num[i]);
		
		cout<<f[limit]<<endl;
	}
	return 0;
}