思路:
很明显,这道题也是一个有依赖的背包问题,关键是怎么去求解。这道题在背包九讲中特别提到了.
还要注意,附件不再有从属于自己的附件,暗示了这种依赖关系只有一层,没有形成一棵树,是最简单的依赖背包
这个问题由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("%d\n",(a)) #define Pf(a) printf("%lf\n",(a)) #define Pl(a) printf("%lld\n",(a)) #define Ps(a) printf("%s\n",(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; }原文链接:https://www.f2er.com/javaschema/283127.html