AcWing 10. 有依赖的背包问题----yxc code
原题链接
困难
作者:
qwer123poiu
,
2019-11-01 09:11:40
,
所有人可见
,
阅读 1799
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m, s;
struct node{ //链式前向星
int to, next;
}ed[N];
int head[N], tot;
int v[N], w[N], dp[N][N];
//dp[i][j]表示选择物品i且体积为j时的最大价值,也是以i为根的整颗子树最大价值
void init(){
tot = 0;
memset(head, -1, sizeof(int)*(n+1));
}
void add(int x, int y){
ed[++tot].to = y;
ed[tot].next = head[x];
head[x] = tot;
}
/*
* 很显然我们若想求得整颗树ans
* 必须先知道子树部分的ans,所以从root出发到达叶节点开始回溯返回ans
* 个人感觉类似于从叶节点回溯建立ans树
* 则ans树的root即为答案
*/
void dfs(int u){
for(int i=head[u]; ~i; i=ed[i].next){//遍历u的所有子节点
int to = ed[i].to;
dfs(to); //要求得节点u ans,必须知道子节点ans
for(int j=m-v[u]; j>=0; --j)
/*
对比01背包for(int j=V; j>=v[i]; --j)
u必选所有必须留下v[u],由于不知道子树的体积必须到0
*/
for(int k=0; k<=j; ++k)
/*
子树to(以to为root的子树)有不同的选点方案。
这些方案可以视为同一分组的不同物品(相对于u节点来说),则子树u有出度个不同分组。
虽然不知道具体的方案,但子树不同的体积就类似于不同方案。(不同选取体积不同)
那么就可以将子树的不同体积视为同一分组的具体物品。
就将问题转换到分组背包问题
对于dp[u][j]而言,他可以不选,或者从to的某一体积转移过去
*/
dp[u][j] = max(dp[u][j], dp[u][j-k]+dp[to][k]);
}
for(int i=m; i>=v[u]; --i) dp[u][i] = dp[u][i-v[u]] + w[u]; //必须选则u结点
for(int i=0; i<v[u]; ++i) dp[u][i] = 0; //体积连v[u]都不足则为0
}
int main(){
cin>>n>>m;
init();
for(int i=1; i<=n; ++i){
int p;
cin>>v[i]>>w[i]>>p;
if(p == -1) s = i;
else add(p, i);
}
dfs(s);
cout<<dp[s][m]<<endl;
}
dp[u][j] = max(dp[u][j], dp[u][j-k]+dp[to][k]);想问一下dp[u][j-k] 会不会包含dp[to][k]所访问的节点
解释的很清晰,赞