AcWing 10. 有依赖的背包问题
原题链接
困难
作者:
fancywing
,
2021-01-19 16:07:51
,
所有人可见
,
阅读 395
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
// 用邻接表存储树型关系,因为树也是一种特殊的图
int e[N],h[N],ne[N], idx;
int n, m;
int f[N][N], V[N], W[N];
void add(int a, int b){
e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
void dfs(int u){
for(int i = h[u]; i !=-1; i = ne[i]){
int son = e[i];
dfs(son);
for(int j = m - V[u]; j>=0; j--){
for(int k = 0; k <= j; k++){
f[u][j] = max(f[u][j], f[u][j-k] + f[son][k]);
}
}
}
// 加上默认选择的父节点价值
for(int i = m; i >= V[u];i--){
f[u][i] = f[u][i-V[u]]+W[u];
}
// 因为我们是从叶子结点开始往上做,所以如果背包容积不如当前物品的体积大,
// 那就不能选择当前结点及其子节点,因此赋值为零
for(int i = 0;i<V[u];i++){
f[u][i] = 0;
}
}
int main(){
cin >> n >> m;
// 初始化邻接表
memset(h, -1, sizeof(h));
int root;
for(int i = 1; i<=n; i++){
int p;
cin>>V[i]>>W[i]>>p;
if(p == -1) root = i;
else add(p, i); // i节点的父亲是p节点
}
dfs(root);
cout<<f[root][m]<<endl;
return 0;
}