动态规划之——背包问题

  前些天在做动态规划的题，感觉动态规划博大精深，没有一种特定的模式，学起来很费劲。在这里就动态规划中的背包问题谈谈。

  三种背包问题：0/1背包，完全背包，多重背包。

  0/1背包：有n件物品和容量为v的背包，求解将哪些物品放入背包中可以使获得的价值最大。

  f[i][v]表示将前i件物品恰好放入容量为v的背包可以获得的最大价值。

1.子问题：将前i件物品放入背包中，若第i件物品不放入背包中，则问题转化为求前i-1个物品放入容量为v的背包；若第i件物品放入背包中，则问题转化为求前i-1个物品放入容量为v-c[i]的背包。

2.转移方程：f[i][v] = max{f[i-1][v], f[i-1][v-c[i]]+w[i]},f[n][v]即为所求。

注意：初始化细节问题，若题目要求恰好装满背包，在初始化时除了f[0]=0,其余设为负无穷；若题目不要求非要装满背包，初始化f[0..v] = 0;

 0/1背包代码：

int DP[14000];
int cost[3403],value[3403];

int main()
{
	int i,v;
	int n,m;
	memset(DP,0,sizeof(DP));
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
		scanf("%d %d",&cost[i],&value[i]);
	for(i=1;i<=n;i++)
	{
		for(v=m;v>=cost[i];v--)
		{
			if(DP[v-cost[i]]+value[i]>=DP[v])
				DP[v]=DP[v-cost[i]]+value[i];
		}
	}
	printf("%d\n",DP[m]);
	return 0;
}

完全背包：有n种物品和容量为v的背包，每种物品可以无限选择，求解将哪些物品放入背包中可获得最大价值。

转化为0/1背包：将第i种物品拆分成费用为c*2^k，价值为w*2^k的若干物品，其中k满足c*2^k<V。这是二进制的思想，因为不管选择几件第i种物品，总可以表示成若干个2^k个物品。但我们有更优的算法，这个算法与0/1背包只有第二重循环的顺序不同。（至于为神马，弄得懂就好，不懂也可以跳过）

 

多重背包：有n种物品和容量为v的背包，第i种物品最多可有n件，求解问题同上。

转化为0/1背包：

将第i种物品分成若干件物品，其中每件物品有一个系数，这个物品的价值和费用是原来的费用和价值乘以这个系数。使这些系数分别为1、2、4、...、2^(k-1)、n-2^k+1，且k是满足n-2^k+1>0的最大整数。例如n=13,则可以分为1、2、4、6。这样就将第i中物品分成了log(n)件。

根据背包九讲，多重背包代码：

#include <iostream>
const int MAX = 100002;
int v;			//背包的容量
int f[MAX];		//背包的最大容量为MAX. f[i][v]表示前i个物品恰放入容量为j的背包获得的最大值,可以优化为f[v]

void multiplePack(int value, int cost, int amount)		//value表示价值，cost表示费用，amount表示物品个数
{
	int i,j,k;
	if(amount*cost >= v)
	{
		//完全背包
		for(i = cost; i <= v; i++)
		{
			if(f[i] < f[i-cost] + value)
				f[i] = f[i-cost] + value;
		}
	}
	else
	{
		k = 1;
		while(k < amount)
		{
			//0/1背包
			for(i = v; i >= k*cost; i--)
			{
				if(f[i] < f[i-k*cost] + k*value)
					f[i] = f[i-k*cost] + k*value;
			}
			amount -= k;
			k = k*2;
		}
		for(i = v; i >= amount*cost; i--)
		{
			if(f[i] < f[i-amount*cost] + amount*value)
				f[i] = f[i-amount*cost] + amount*value;
		}
	}
}

int main()
{
	int n;
	int i,j;
	int num,value;
	while(scanf("%d",&v) != EOF)
	{
		memset(f,0,sizeof(f));
		scanf("%d",&n);
		for(i = 1; i <= n; i++)
		{
			scanf("%d %d",&num,&value);
			multiplePack(value,value,num);
		}
		printf("%d\n",f[v]);
	}
	return 0;
}

 

参见poj3624 1276