P1064 金明的预算方案

输入 

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出 

2200

解析

   这道题是一道依赖背包问题，所谓依背包就是i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。

   题目中是附件依赖与主件，并且附件没有继续下去的附件，所以这是一题非树形有依赖的背包问题。

思路

  我们首先知道，要选附件一定要选它对应的主件，所以我们首先要建立两者的对应关系，也就是附件放到主件的数组下：

struct node{
	int v,p,q;
}arr[1001];
vector<node> pri[30222];
int dp[30222],V[60][1000],P[60][100],cnt[60];
int n,m,ans;

cin>>n>>m;
for(int i=1;i<=m;i++)
{
	cin>>arr[i].v>>arr[i].p>>arr[i].q;
	if(arr[i].q>0)
	{
		pri[arr[i].q].push_back(arr[i]);
	}
}

   这样，其实我们实现了以主件为索引的分组，然后下一步我们需要做的就是，我们可以把每组的附件进行01背包处理，为什么呢？我们01背包处理的目的就是得出在购买此主件的情况下，我们如何购买附件才有最大利润。对于每一个附件，都是两种情况，买和不买：

   不买：dp[k]=dp[k]

   买：dp[k]=dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p

   我们对于每一个主件，都有两种选择，一是只选主件，二是选这个主件和它的一些附件

for(int i=1;i<=m;i++)
{
	if(arr[i].q==0)//如果是主件的话
	{
		memset(dp,-1,sizeof(dp));//恰好背包的铺垫
		dp[0]=0;//恰好背包
		for(int j=0;j<pri[i].size();j++)//循环当前主件的所有附件数量
		{
			//01背包的模板思想，但这里是从n-arr[i]开始，因为我们能买这些附件的前提就是要先买对应的主件arr[i]
			for(int k=n-arr[i].v;k>=pri[i][j].v;k--)
			{
				//这里也就是dp[k]=max(dp[k],dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p)
				if(dp[k]<dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p&&dp[k-pri[i][j].v]!=-1)//前提还要dp不等于-1，也就是有恰好买够过
				{
					dp[k]=dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p;
				}
			}
		}
		//然后因为我们每次循环都需要重新memset一下dp数组，所以要保存一下dp状态
		for(int j=0;j<=n-arr[i].v;j++)
		{
			if(dp[j]!=-1)//恰好背包的判断
			{
				cnt[i]++;
				V[i][cnt[i]]=j+arr[i].v;//信息1
				P[i][cnt[i]]=arr[i].v*arr[i].p+dp[j];//信息2
			}
		}
	}
	if(arr[i].q==0)//信息3   只买主件
	{
	    cnt[i]++;
	    V[i][cnt[i]]=arr[i].v;
	    P[i][cnt[i]]=arr[i].v*arr[i].p;
	} 
}

注释里面的两个信息：

   前提：cnt[i]就是主件i的所有组合数量，注意是组合数量不是附件，因为01背包解决的问题就是每种物品只能取一次的情况下，可以选择不同的多件物品，怎么组合才能价值最大。比如主件A有附件B、C，那么在价格都可以承受的情况下，可以的组合是A+B、A+C、A+B+C

   信息1：我们的上一层循环是从0~n-arr[i]，因为这时候我们是需要选择这个主件和它的附件，所以我们将主件配对几种附件价格的总和储存在V数组里面，相当于上面A+B的价格或者A+C、A+B+C。这句话需要理解进去，因为背包问题都是在数组里面保存所有状态，并且j+arr[i].v的范围是从arr[i].v~n，也就是当前主件的价格到总价格

   信息2：这里储存的是购买当前主件(arr[i].v*arr[i].p)和当前主件的附件(dp[j])的最大价值和

   信息3：这里是只买主件的状态。所以V数组只需要储存当前主件的价格，P数组只要储存当前主件的价值

最后，我们需要做的是分组背包的计算，基本思路就是循环每个主件，在所有的价格范围下，也就是j：0~n的范围下，对于每个能承受的价格j，循环当前主件的所有组合，然后max出选这个组合(dp[j-V[i][k]]+P[i][k])价值比较大还是不选(dp[j])比较大。

memset(dp,0,sizeof(dp));
for(int i=1;i<=m;i++)
{
	for(int j=n;j>=0;j--)
	{
		for(int k=1;k<=cnt[i];k++)
		{
			if(j>=V[i][k])
			{
				dp[j]=max(dp[j],dp[j-V[i][k]]+P[i][k]);
			}
		}
	}
}

这边没有判断是否是主件，因为如果是附件的话，他的cnt[i]就会是0，所以直接跳过了

最后，只要在dp数组里面寻找到最大的那个值就可以了

for(int i=0;i<=n;i++)
{
	ans=max(ans,dp[i]);
}
cout<<ans<<endl;

贴上总代码：

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cstring>
#include <algorithm>
using namespace std;
struct node{
	int v,p,q;
}arr[1001];
vector<node> pri[30222];
int dp[30222],V[60][1000],P[60][100],cnt[60];
int n,m,ans;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>arr[i].v>>arr[i].p>>arr[i].q;
		if(arr[i].q>0)
		{
			pri[arr[i].q].push_back(arr[i]);
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(arr[i].q==0)//如果是主件的话
		{
			memset(dp,-1,sizeof(dp));//恰好背包的铺垫
			dp[0]=0;//恰好背包
			for(int j=0;j<pri[i].size();j++)//循环当前主件的所有附件数量
			{
				//01背包的模板思想，但这里是从n-arr[i]开始，因为我们能买这些附件的前提就是要先买对应的主件arr[i]
				for(int k=n-arr[i].v;k>=pri[i][j].v;k--)
				{
					//这里也就是dp[k]=max(dp[k],dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p)
					if(dp[k]<dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p&&dp[k-pri[i][j].v]!=-1)//前提还要dp不等于-1，也就是有恰好买够过
					{
						dp[k]=dp[k-pri[i][j].v]+pri[i][j].v*pri[i][j].p;
					}
				}
			}
			//然后因为我们每次循环都需要重新memset一下dp数组，所以要保存一下dp状态
			for(int j=0;j<=n-arr[i].v;j++)
			{
				if(dp[j]!=-1)//恰好背包的判断
				{
					cnt[i]++;
					V[i][cnt[i]]=j+arr[i].v;//信息1
					P[i][cnt[i]]=arr[i].v*arr[i].p+dp[j];//信息2
				}
			}
		}
		if(arr[i].q==0)//只买主件
		{
			cnt[i]++;
			V[i][cnt[i]]=arr[i].v;
			P[i][cnt[i]]=arr[i].v*arr[i].p;
		} 
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=m;i++)
	{
		for(int j=n;j>=0;j--)
		{
			for(int k=1;k<=cnt[i];k++)
			{
				if(j>=V[i][k])
				{
					dp[j]=max(dp[j],dp[j-V[i][k]]+P[i][k]);
				}
			}
		}
	}
	for(int i=0;i<=n;i++)
	{
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
	system("pause");
	return 0;
}