POJ1276-多重背包

说到背包问题，都少不了网上很出名的背包九讲。我也是看了那个以后才知道怎么做的。

多重背包：就是在0 1背包的基础上，有的物品可能有多个，问你怎么选才能使总价值最大。

我们最容易想到的是把相同的物品分开，比如说有n个a1物品 就将它分成 a1 a2 a3 ...an 然后再用01背包的方法去解决。不过在此题中，重复的物品可能有很多个，所以这样会超时。

在背包九讲中提出了一种方法：若某物品n[i]个 ，那么我们得到一串系数1 2 4  ...2 ^(k-1) ,n[i]-2^k+1 其中k为满足n[i]-2^k+1>0的最大整数，比如13拆成1 2 4 6 ，将这种物品分成4个物品，每个物品的价值和重量均在原基础上分别乘以得到的系数。

这种分解方法比原来的方法有很大的改进

下面是代码

 

 

#include<iostream>
using namespace std;
#define MAXSIZE 100010
#define MAX(a,b) (a>b?a:b)
int cash,n;
int tn;
int num[1010];
int d[1010];
int w[10010];
int dp2[MAXSIZE];

//背包九讲

int getpow(int p)
{
	if(!p)
		return 1;
	int at=1;
	while(p--)
		at=at<<1;
	return at;
}

int getk(int ni)
{
	int k=0;
	int old=0;
	while(ni+1>getpow(k))
	{
		old=k;
		k++;
	}
	return old;
}

void fenjie()
{
	tn=1;
	memset(w,0,sizeof(w));
	memset(dp2,0,sizeof(dp2));
	for(int i=1;i<=n;i++)
	{
		int tt=num[i];
		//得到最大系数k
		int k=getk(num[i]);
		//分解
		int rate;
		for(int j=0;j<k;j++)//0->(k-1)
		{
			rate=getpow(j);
			w[tn++]=rate*d[i];
		}
		rate=num[i]-getpow(k)+1;
		w[tn++]=rate*d[i];
	}
}

int slove()
{
	tn--;
	//多重背包问题
	for(int i=tn;i>=1;i--)
	{
		for(int j=cash;j>=1;j--)
		{
			if(w[i]<=j)//放的下
			{
				dp2[j]=MAX(dp2[j],dp2[j-w[i]]+w[i]);
			}
			
		}
		
	}
	return dp2[cash];
}

int main()
{
	while(scanf("%d",&cash)!=EOF)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&num[i],&d[i]);
		}
		//拆开
		fenjie();
		//背包
		printf("%d\n",slove());
		
	}
	return 0;
}