赞

马老师70多岁了还来学算法啊？

马老师年轻时候也是ICPC的一员猛将

年轻人，活到老，学到老

对不起马老师我不懂规矩,我今后一定耗子尾汁好好反思😭

为什么j倒着枚举k正着枚举？
看到评论区讨论了一下但是没看到比较清晰的答案。
k的话正反无所谓，j倒着枚举自认为是降维，但是降得是第二维，不降的话第一维是目前要求的节点（x），第二维是遍历到目前节点的第i个子树，第三维是体积j
也就是说f[x][i][j] 的意义是 x这颗树遍历到第i个子树时体积为j的最大价值
同一颗子树的结果不能互相影响，所以j从大往小更新
不降维的话状态转移应该是

f[x][i][j] = max(f[x][i-1][j],f[x][i-1][j-1],...,f[x][i-1][v[x]])

感谢，非常清晰！

是的，这种思路更为流畅，y总的需要打补丁

感謝肯定！

补丁一次感觉用的很恰当
y总的代码没有先把根节点算进去导致后面需要打两个补丁分别为
1.将根节点算进去
2.将所有小于根节点体积的情况赋0
而帖主的思路先将根节点放进去，然后再算去掉根节点体积后的背包里能放的最大价值，就避免了计算不符合的情况

确实，这样的话就直接不用后面的补丁了，虽然补丁很妙，但是没有补丁感觉思维更流畅

这个j倒着循环有门道。。

哦。。。我傻了 原来是因为省掉了一维

这个应该叫滚动数组优化

这里优化了哪一维？不是还是两维吗

优化了，是三维优化成两维，原来是对于前 i 组 体积不超过 j 选 k 的选法，现在把 i 用用滚动数组优化了，所以要倒序枚举

tql，原来没有理解为啥f[x][j-k]+f[y][k]可以表示减去y这个子树剩余子树的最大价值，发现是三维优化减少一维变成滚动数组时候就理解了，orz

是哪三维啊 ，没看懂为什么 j=m;j>=v[x];j–

能详细说一下吗

k一维,son一维，体积一维

两个大佬的大体思路都是一样， 不过你这个更加简洁呢，谢谢大佬分享

### 不敢妄称大佬呀

这里的dp状态是包含根节点的状态，而y总dp的时候没有考虑进根节点，最后再打补丁！

其实dfs可以再加一个体积参数

int dfs(int x,int m)
{
    for(int i=v[x];i<=m;i++) f[x][i]=w[x];//点x必须选，所以初始化f[x][v[x] ~ m]= w[x]
    for(int i=0;i<g[x].size();i++)
    {
        int y=g[x][i];
        dfs(y,m-v[x]);
        for(int j=m;j>=v[x];j--)//j的范围为v[x]~m, 小于v[x]无法选择以x为子树的物品
        {
            for(int k=0;k<=j-v[x];k++)//分给子树y的空间不能大于j-v[x],不然都无法选根物品x
            {
                f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);
            }
        }
    }
}

这样就会少循环一些，少计算一些不必要的数据。

dfs(y,m-v[x]);
这就很奈斯

可以在开头判断m的值减少递归次数

为什么 f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);这里我改成 f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]+w[x]);然后去掉最开始的给f[x]层赋值就不行了呢？

### 这样理解哪里出了漏洞呢,我递归完子树之后,直接求u在对应体积下的最大值不就可以了吗？

void dfs(int u)
{
    if (h[u] == -1)
    {
        for (int j = m; j >= v[u]; j--)
        {
            f[u][j] = w[u];
        }
        return;
    }
    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--)
        {
            f[u][j] = max(f[u][j], f[son][j]);
        }
    }
    for (int j = m; j >= v[u]; j--)
    {
        f[u][j] = f[u][j - v[u]] + w[u];
    }
    for (int j = 0; j < v[u]; j++)
        f[u][j] = 0;
}

 for (int j = m - v[u]; j >= 0; j--)
        {
            f[u][j] = max(f[u][j], f[son][j]);
        }

你这只能选1个子结点啊

什么意思兄弟？

比如到子树u这有多个儿子结点, 你这个更新最后只会选出max(f[son][j]），没法累加到一起。

兄弟我终于理解了,之前一直觉得用单纯用01背包的思路就可以,但是这样确实求的只是子节点在对应体积下的最大值,不能累加到一起,所以还要继续把每个子树分类,确实,感谢

我想说一下，这里的dfs是用void做返回值，习惯不可变

对的 用int，有些oj会tle

vs编译都过不了，用int没返回值

相同的思路你的代码看起来更容易理解 谢分享（以后所有ACwing上的算法就统称DXC高级算法吧）

import java.util.Scanner;

//TIP 要[HTML_REMOVED]运行[HTML_REMOVED]代码，请按 [HTML_REMOVED] 或
// 点击装订区域中的 [HTML_REMOVED] 图标。
public class Main {
public static int N ;
public static int V ;
public static int[] v= new int[109];
public static int[] w= new int[109];
public static int[] p= new int[109];
public static int[] exit= new int[109];
public static int[][] f = new int[109][109];
public static boolean dfs(int i,int j){
if(p[i]!=-1) {
if (exit[p[i]] == 0) {
if (j >= v[p[i]]) {
f[i][j] += w[p[i]];
if(dfs(p[i], j)){
return true;
}
} else
return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
V = sc.nextInt();
v = new int[109];
w = new int[109];
p = new int[109];
exit= new int[109];
int[][] f = new int[109][109];
for (int i = 1; i <= N; i) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
p[i] = sc.nextInt();
}
for(int i = 1; i <= N; i){
for(int j = 0; j <= V; j++){
f[i][j] = f[i-1][j];
if(j>=v[i]){
f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);
if(f[i-1][j]<f[i-1][j-v[i]]+w[i]){
exit[i] = 1;//选择第i个点
if(!dfs(i,j)){
exit[i] = 0;
f[i][j] = f[i-1][j];
}
}
}
}
}
System.out.println(f[N][V]);

}

}为什么测试结果是13呢

orz

这个dfs爱了

前几年写的题解，那时候用acwing的人还不多

和我的思路差不多 y总想了好久才明白啥意思
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]

#define PII pair[HTML_REMOVED]

using namespace std;

const int N = 110;
int n, m;
int v[N], w[N];
struct Edge {
int to, next;
}ed[N];
int cnt;
int head[N];
void add(int u , int v)
{
ed[++cnt].to = v;
ed[cnt].next = head[u];
head[u] = cnt;
}
int f[N][N];

void dfs(int u)
{
for (int i = v[u]; i <= m; i ++ ) f[u][i] = w[u];
for (int i = head[u]; i ; i = ed[i].next)
{
int son = ed[i].to;
dfs(son);

    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[son][k]);
    }
}

}
int main()
{
cin >> n >> m;
int p;
int root = -1;
for (int i = 1; i <= n; i ++ )
{
cin >> v[i] >> w[i] >> p;
if (p == -1) root = i;
else add(p, i);
}
dfs(root);

cout << f[root][m];

return 0;

}

太清晰了 一下子就看懂了 Orz

极赞，我就觉得自己代码和y总对不上（呜呜）

妙啊

vector万岁