P1064 [NOIP2006 提高组] 金明的预算方案
P1064 [NOIP2006 提高组] 金明的预算方案
题意：
每个物品有价格和价值，物品之间存在依赖关系（单向的），现在又n元钱，买哪些物品，即满足依赖关系又使得每件物品的价格与价值的乘积的总和最大
（每个主件最多两个附件）
题解：
方法一：
学习博客
因为每个主件最多两个附件，且附件必须依赖于主件，所以对每个主件一共就五种决策：
1.不选，然后考虑下一个
2.选择且只选主件
3.选择这个主件，且选择附件1
4.选择这个主件，且选择附件2
5.选择这个主件，且选择附件1，2
我们设变量fv[i][j]表示主件为i的第j个附件的价值与重量乘积
fw[i][j]表示主件为i的第j个附件的重量
dp[i]就是01背包中的设定
我们仿照01背包对上面5种情况列出转移方程
方法2：
学习文章
根据依赖关系我们可以得知这是一个树型结构，这个树的特点：
一个物品所依赖的所有物品都是他的父节点
如果一个物品不选,对应到树上,他所有的子节点都不能选
现在我们如何用01背包来解决这个树形问题
我们可以将树转化成链，通过dfs序实现
对树求后序遍历，后序遍历的顺序是前后中，也就是一个节点的儿子和左兄弟都在他前面
这样我们可以有以下决策:
1.选当前物品，状态i由i-1（从儿子）转移而来
2.不选择，这个点的儿子也不能选，那状态只能从前面最近的左兄弟转移
pre[u]表示编号为u的左兄弟的编号
dp[i][j]=max(dp[pre[i]][j],dp[i-1][j-v]+w)
总复杂度为O(n+nm),关键是这个方法可以解决附件上有附加的情况，能处理情况更广
不过我对这个方法还不是完全理解。。有待消化
代码：
#include<iostream> using namespace std; int m,n,mw[33333],mv[33333],fw[33333][3],fv[33333][3],dp[33333],v,p,q; //mw主件重量，mv主件价值，fw主件对应的附件重量，fv主副价值，n总重量，m总个数 int main() { cin>>n>>m; for(int i=1;i<=m;i++){ cin>>v>>p>>q; if(!q){//如果是主件 mw[i]=v;//主件重量 mv[i]=v*p;//主件价值与重量乘积 } else{//如果是附件 fw[q][0]++;//记录主件的附件个数（只记录在fw就行，fv那里没用 fw[q][fw[q][0]]=v;//主件的个数是用来确定该附件应该填在第一个还是第二个格子里 fv[q][fw[q][0]]=v*p;//（是第一个还是第二个附件） } } for(int i=1;i<=m;i++) for(int j=n;j>=mw[i];j--){//01背包模板 //每一个if的前提是背包能不能装下该物品 //情况1：只要主件 和啥都不要比较 dp[j]=max(dp[j],dp[j-mw[i]]+mv[i]); //情况2：主件和附件1 和上面选出的较大值比较 if(j>=mw[i]+fw[i][1])dp[j]=max(dp[j],dp[j-mw[i]-fw[i][1]]+mv[i]+fv[i][1]); //情况3：主件和附件2 和上面选出的较大值比较 if(j>=mw[i]+fw[i][2])dp[j]=max(dp[j],dp[j-mw[i]-fw[i][2]]+mv[i]+fv[i][2]); //情况4：都要 if(j>=mw[i]+fw[i][1]+fw[i][2]) dp[j]=max(dp[j],dp[j-mw[i]-fw[i][1]-fw[i][2]]+mv[i]+fv[i][1]+fv[i][2]); } //输出在价值为n时能得到的最大值 cout<<dp[n]<<endl; return 0; } #include <cstdio> #include <algorithm> using namespace std; const int maxn = 64; const int maxm = maxn; const int maxv = 33333; struct Node{//表示物品int v,w;Node() = default;Node(int a,int b):v(a),w(b){} }d[maxn],t[maxn]; struct Edge{int from,to;Edge() = default;Edge(int a,int b):from(a),to(b){} }Edges[maxm]; int head[maxn],nxt[maxm],root[maxn],rp; inline void addedge(int from,int to){static int tot;Edges[++tot] = Edge(from,to);nxt[tot] = head[from];head[from] = tot; } int pre[maxn],f[maxn][maxv],p = 0; void dfs(int u){int tp = p;//由于后序遍历的性质,一个点的左兄弟显然是进入这个点时序列中的最后一个点for(int i = head[u];i;i = nxt[i]){Edge &e = Edges[i];dfs(e.to);}d[++p] = t[u];//后序遍历pre[p] = tp;//求左兄弟,注意,pre[t]表示序列中编号为t的节点的左兄弟的编号 } int n,m; int main(){scanf("%d %d",&m,&n);for(int i = 1;i <= n;i++){//建图int v,w,faz;scanf("%d %d %d",&v,&w,&faz);t[i] = Node(v,v * w);//先预处理它的权值addedge(faz,i);//有个技巧,如果一个点是主件,我们就认为它依赖于虚拟点0}dfs(0);for(int i = 1;i <= n;i++)//dp求解for(int j = 0;j <= m;j++)if(j >= d[i].v)f[i][j] = max(f[pre[i]][j],f[i - 1][j - d[i].v] + d[i].w);else f[i][j] = f[pre[i]][j];//转移 printf("%d\n",f[n][m]);return 0; }总结
以上是生活随笔为你收集整理的P1064 [NOIP2006 提高组] 金明的预算方案的全部内容，希望文章能够帮你解决所遇到的问题。
