分析
二叉苹果树是有依赖的背包问题的一种变形,后者每个选取的物品是每个节点,前者是每条边
虽然状态转移方程不同,但其集合的划分是相似的
f[u][j]:以u为根节点,选择若干物品(边/节点)背包容量不超过j的最大价值
异同
二叉苹果树:f[u][j]=max(f[u][j],f[u][(j-1)-k]+f[v][k]+w)(初始化为0/不初始化)
f[u][j]表示以u为根节点,以j为体积的方案,
首先j=m~0,因为需要预留一个和父子节点的边的所以k=0-j-1(空下一个空间放边)
子节点能用的体积是k,父节点能用的体积是j-1-k(相加为j-1)
那f[u][j]就等于节点为u,体积为j-1-k的最大值+节点为v,体积为j-1-k的最大值+父子边的权值
有依赖的背包问题:f[u][j]=max(f[u][j],f[u][j-k]+f[i][k])(需要初始化)
f[u][j]表示以u为根节点,以j为体积的方案,
首先j=m~v[u],因为需要预留一个和父节点的权值(一定要选择根节点)
同理k=0-j-v[u],与有依赖的背包问题区别的一点是不用空下一个空间
子节点能用的体积是k,父节点能用的体积是j-k(相加为j)
建图方式
在有明确根节点的情况下,有向图和无向图都可,只是遍历判断不同
无向图会搜索到父节点,需要额外标记(这也是TLE或MLE的原因)
有向图不会搜索到父节点,不需要额外标记
具体代码如下
苹果树
#include<iostream>
#include<vector>
#include<map>
using namespace std;
struct E{
int v,w;
};
int n,m;
map<int,vector<E>>g;
int f[105][105];
void dfs(int u,int p)
{
for(auto i:g[u])
{
int v=i.v,w=i.w;
if(v==p)continue;
dfs(v,u);
for(int j=m;j>=0;j--)
for(int k=0;k<j;k++)
f[u][j]=max(f[u][j],f[u][(j-1)-k]+f[v][k]+w);
//f[u][j]表示以u为根节点以j为体积的方案,
//首先j=m~1,因为预留一个和字节点相关的所以k=0-j-1,
//子节点能用的体积是k,父节点就是j-1-k
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<n;i++)
{
int u,v,c;
cin>>u>>v>>c;
g[u].push_back({v,c});
g[v].push_back({u,c});//无向图存俩边,标记父节点,单向图存一个边,不标记父节点
}
dfs(1,-1);
cout<<f[1][m]<<endl;
}
背包
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int n,m;
map<int,vector<int>>g;
map<int,int>v,w;
int f[105][105];
void dfs(int u)
{
for(int i=v[u];i<=m;i++) f[u][i]=w[u];//点u必须选,所以初始化f[u][v[u] ~ m]= w[x]
for(auto i:g[u])
{
dfs(i);
for(int j=m;j>=v[u];j--)
for(int k=0;k<=j-v[u];k++)
f[u][j]=max(f[u][j],f[u][j-k]+f[i][k]);
}
}
int main()
{
cin>>n>>m;
int root=0;
for(int i=1;i<=n;i++)
{
int u;
cin>>v[i]>>w[i]>>u;
g[u].push_back(i);
//g[i].push_back(u);
if(u==-1)
root=i;
}
dfs(root);
cout<<f[root][m]<<endl;
}
orz