HDU 3449 Consumer（依赖背包）

自己的思路是：参考了背包九讲，用01背包初始化每一组背包，然后用分组背包写，不过悲剧的超时了；于是参考别人的代码写了写，不过理解不是很好

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define max(a,b) a > b ? a : b
#define clr(arr,val) memset(arr,val,sizeof(arr));
int dp[51][100005];
int baggroup,money;
void zeroonepack(int group,int cost,int value,int v)
{
	for(int i = v;i >= cost ;i--)
	{
		dp[group][i] = max(dp[group][i],dp[group][i - cost] + value);
	}
};
int dp2[100005];
int main()
{
	freopen("in.txt","r",stdin);
	freopen("out1.txt","w",stdout);
	while(~scanf("%d%d",&baggroup,&money))
	{
		clr(dp2,0);
		clr(dp,0);
		for(int i = 1; i <= baggroup;i++)    //物品组
		{
			int bagcost,bagnum;
			scanf("%d%d",&bagcost,&bagnum);
			for(int j = 1;j <= bagnum ;j++)
			{
				int tmp1,tmp2;
				scanf("%d%d",&tmp1,&tmp2);
				zeroonepack(i,tmp1,tmp2,money - bagcost);
			}
			for(int j = money - bagcost;j >= 0;j--)   // 将花费为bagcost，价值为0的盒子分别加到n个物品组中，最后这个物品组中还是只有n个物品（这里的物品可能是由很多物品组成的）
			{
				dp[i][j + bagcost] = dp[i][j] + 0;
				dp[i][j] = 0;
			}
			for(int j = money;j >= bagcost  + 1;j--)   //钱
			{
				for(int k = bagcost + 1 ;k <= money;k++)   //物品组中的物品
				{
					if(j - k >= 0)
					{
						dp2[j] = max(dp2[j],dp2[j - k] + dp[i][k]);
					}
				}
			}
		}
		printf("%dn",dp2[money]);
	}
	return 0;	
}

参考大牛写的代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define max(a,sizeof(arr));
int dp[51][100005];
int bagGroup,money;
int main()
{
	//freopen("in.txt",stdin);
	//freopen("out1.txt",&bagGroup,&money))
	{
		clr(dp,0);
		for(int i = 1; i <= bagGroup;i++)    //物品组
		{
			int c[15],v[15];
			int bagCost,bagNum;
			scanf("%d%d",&bagCost,&bagNum);
			for(int j = 1;j <= bagNum;j++)
				scanf("%d%d",&c[j],&v[j]);
			for(int  j =0;j <= bagCost;j++)
				dp[i][j] = -9999999;
			for(int j = bagCost;j <= money;j++)   //在第i组中先买盒子（买得起的就买）
				dp[i][j] = dp[i-1][j-bagCost] ;
			for(int j = 1;j <= bagNum ;j++)
			{
				for(int k = money; k >= c[j] ;k--)
				{
					dp[i][k] = max(dp[i][k],dp[i][k-c[j]] + v[j]);
				}
			}
			for(int j = 0;j <= money;j++)
				dp[i][j] = max(dp[i][j],dp[i-1][j]);
		}
		printf("%dn",dp[bagGroup][money]);
	}
	return 0;	
}