蓝桥杯 金明的预算方案 有依赖的背包

题目链接

思路:

很明显,这道题也是一个有依赖的背包问题,关键是怎么去求解。这道题在背包九讲中特别提到了.

还要注意，附件不再有从属于自己的附件，暗示了这种依赖关系只有一层，没有形成一棵树，是最简单的依赖背包

这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法，将不依赖于别
的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所
有的物品由若干主件和依赖于每个主件的一个附件集合组成。
按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包
括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件……
无法用状态转移方程来表示如此多的策略。（事实上，设有n个附件，则策略有2
n + 1个，为指数
级。）
考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的
附件集合实际上对应于P06中的一个物品组，每个选择了主件又选择了若干个附件的策略对应
于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步
转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。
再考虑P06中的一句话：可以对每组中的物品应用P02中“一个简单有效的优化”。这提示我
们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，
我们可以对主件i的“附件集合”先进行一次01背包，得到费用依次为0..V-c[i]所有这些值时相应
的最大价值f’[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组，其中费
用为c[i]+k的物品的价值为f’[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通
过一次01背包后，将主件i转化为V-c[i]+1个物品的物品组，就可以直接应用P06的算法解决问题
了。

下面我们要做的就是按照上面的说法去一点点求.我们开一个二维数组 dp[i][j] 表示对第i个主件的附件先进行一次01背包,然后再把主件强加进去,最后开一个一维数组f跑遍01背包去维护最优解,一共需要三次背包.

有一点点优化需要注意的是:

题目中已经明确指出所有的物品都是10的倍数如果我们不优化那样肯定会超时,所以我们将所给的钱数和每个物品的价钱缩小十倍求最优解.

#include<bits/stdc++.h>
#define Ri(a) scanf("%d",&a)
#define Rl(a) scanf("%lld",&a)
#define Rf(a) scanf("%lf",&a)
#define Rs(a) scanf("%s",a)
#define Pi(a) printf("%dn",(a))
#define Pf(a) printf("%lfn",(a))
#define Pl(a) printf("%lldn",(a))
#define Ps(a) printf("%sn",(a))
#define W(a) while(a--)
#define CLR(a,b) memset(a,(b),sizeof(a))
#define MOD 100000007
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+1e3;
int dp[66][3*maxn],f[maxn*3];
int n,m;
struct node
{
	int v,p,q;
}l[66];
int main()
{	
	CLR(dp,-1);
	dp[0][0]=0;
	Ri(n),Ri(m);
	n/=10;
	for(int i=1;i<=m;i++)
		{
		  Ri(l[i].v),Ri(l[i].p),Ri(l[i].q);
		  l[i].v/=10;
		  dp[i][0]=0;
		}
		for(int i=1;i<=m;i++)
		{
			if(l[i].q==0)
			continue;
			for(int j=n;j>=l[i].v;j--)
			{
				if(dp[l[i].q][j-l[i].v]!=-1)
				dp[l[i].q][j]=max(dp[l[i].q][j],dp[l[i].q][j-l[i].v]+l[i].v*l[i].p);
			}
		}
		for(int i=1;i<=m;i++)
		{
			if(l[i].q!=0)
			continue;
			for(int j=n;j>=l[i].v;j--)
			{
				if(dp[i][j-l[i].v]!=-1)
				dp[i][j]=max(dp[i][j],dp[i][j-l[i].v]+l[i].p*l[i].v);
				dp[i][j-l[i].v]=-1;
			}
		}
		CLR(f,-1);
		f[0]=0;
		int ans=0;
		for(int i=1;i<=m;i++)
		{
			if(l[i].q!=0)
			continue;
			for(int j=n;j>=l[i].v;j--)
			{
				for(int k=j;k>=l[i].v;k--)
				{
					if(dp[i][k]!=-1&&f[j-k]!=-1)
					{
						f[j]=max(f[j],dp[i][k]+f[j-k]);
						ans=max(ans,f[j]);
					}
				}
			}
		}
		Pi(ans*10);
	return 0;
 }

一开始我就想,我以前做的初值初始化为-inf 或-1 的不都是满包问题吗,即某些状态根本不存在的,对于这个题也没有什么一定不存在的状态把.后来我就想 因为我们是先对附件进行了背包 然后在把主件强加进去,这个过程中肯定是价钱越小价值越大越好啊,而且这样可以排除那些 对于同样的价值，我们取背包的重量越轻越好留下更多的钱买更多的东西.虽然根本没什么影响.

还有一点比较巧的就是,当我们把主件强加到背完一次包的附件当中取的时候,把附件的背包值变为-1,就会使得后面用f数组更新最有解时,全是强加到附件以后的背包状态.这个地方会有影响,如果不恢复成-1

而且这样会减少计算量,否则的话会超时.

改成下面这样就可以过,但是有两个点超时....优化的也不是很多

#include<bits/stdc++.h>
#define Ri(a) scanf("%d",0);
	dp[0][0]=0;
	Ri(n),Ri(l[i].q);
		  l[i].v/=10;
		  dp[i][0]=0;
		}
		for(int i=1;i<=m;i++)
		{
			if(l[i].q==0)
			continue;
			for(int j=n-l[l[i].q].v;j>=l[i].v;j--)
			{
				//if(dp[l[i].q][j-l[i].v]!=-1)
				dp[l[i].q][j]=max(dp[l[i].q][j],dp[l[i].q][j-l[i].v]+l[i].v*l[i].p);
			}
		}
		for(int i=1;i<=m;i++)
		{
			if(l[i].q!=0)
			continue;
			for(int j=n;j>=l[i].v;j--)
			{
				//if(dp[i][j-l[i].v]!=-1)
				dp[i][j]=max(dp[i][j],f[j]);
					}
				}
			}
		}
		Pi(ans*10);
	return 0;
 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!