7

(个人感觉：算法用java写通俗易懂，网上的我表示根本看不懂)

翻译：先上图

这个题的第一个输入样例是，你有10个兵，每个兵可以解决20个虫子，有5个房间，这5个房间像这样的一棵树连接起来的，起点是1号房间。每个房间有几只虫子和几个大脑。如第一个伤50就是意思有50个虫子，得10就是可以得到10个大脑。你走过这个房间，就必须把你的士兵留下来几个跟虫子作战。比如50个虫，你的就要放3个士兵在这个房间。就是问你，这个路线怎么个安排法，你能获得最多的大脑。（走过了就不可以回头，不存在走到了子节点又返回父节点，然后再去到另一个子节点）

思维概括：动态规划->假设后面都是最优解 可能这样讲还是有点抽象 我们的做法是对每个字节点递归取得最优解，进行比较，取得最大值，就是我们要的答案了->那么这个最优解又是怎么取的呢？需要到底层去举个例 上图

如果我们执行到一个拥有4个子节点的节点，毫无疑问，我们只需要调用这个递归方法，把这个点和当前剩余数量放进去即可。

再执行到子节点。这里假设这些字节点都没有后续的子节点了，那么就是要和这个子节点进行比对，如果士兵数量满足，那么这个最底层的递归结果就是返回这个节点的大脑个数。如果不满足，返回0.所以这样就求出最优解了。因为子节点已经没有子节点了，这里进行的判断就是最优解。再把这4个的大脑个数进行比较即可。

可能你感觉还不是很靠谱，那么我们再假设这4个子节点中的某一个子节点后续仍然有一个子节点。那么这种情况肯定要继续递归了，难道这种情况不像我们这里讨论的情况一样吗？就算子节点的子节点还是有子节点，还是一样。逃不开这种形式。

上代码

//经典树形背包问题，利用动态规划
//没看懂可以评论一下，或者+q136284008，我会花大力气从本质上，以最简单的形式讲解递归以及这里的递归

public class StarshipTroopers1011 {

    private static TreeNode father;

    private static int troopsNumber = 10;

    public static void main(final String[] args) throws Exception {

        initData();

        int result = calculateCurrentBest(father, troopsNumber);

        System.out.println(result + "");
    }

    private static void initData() {
        father = new TreeNode(50, 10);
        father.addChild(40, 10);
        father.addChild(40, 10);

        TreeNode son1 = father.getChildList().get(0);

        son1.addChild(65, 30);
        son1.addChild(70, 30);
    }

    //重点理解最优情况：
    //就是假设后面都已经取到最优的情况(这个最优的情况在这里具体是什么情况？)，
    //即传入当前节点，当前数目，你这么点兵可以赚的极限就是这个递归的结果
    //所以分析到这里，返回给你的应该是int，最赚的情况，有几个大脑
    private static int calculateCurrentBest(TreeNode node, int number) {
        //先判断当前这个节点够不够,想像最开始传进来的父节点，和数目，结果它满足不了
        //这样想 逻辑是不是没有错？
        int brainGet = 0;
        if (node.getTroopersNeed() > number) {
            return 0;
        } else {
            brainGet += node.getBrainHave();
            number -= node.getTroopersNeed();
        }

        //若这个点没有儿子
        if (node.getChildList().size() == 0) {
            if (node.getTroopersNeed() > number) return brainGet;
            else {
                brainGet += node.getBrainHave();
                return brainGet;
            }
        }

        //有儿子，对每个儿子进行比较（因为题目要求士兵不可以回头）
        int max = 0;
        List<TreeNode> list = node.getChildList();
        for (TreeNode t : list) {
            int partMax = calculateCurrentBest(t, number);
            if (max < partMax) {
                max = partMax;
            }
        }
        brainGet += max;

        //是不是感觉不靠谱？考虑这样一种情况：1个点 4个儿子 calculateCurrentBest执行到这个点
        //就会执行底部的代码块，让子的去查询最优解，（只要你有儿子就要继续递归）现在就来看看
        //是不是没儿子的情况可以得出最优解：1，2，3，4 4个儿子分别执行， 会执行中间的代码
        //块，有要不起（0），和返回这个点的大脑数量，谁返回的多，就要谁！底层都可以执行最优解
        //父层自然也可以以此得出最优解，所以动态规划的最优解是建立在底层极端情况建立的，不要
        //把她想的那么复杂，可怕
        //递归考虑底层情况就会容易理解！
        return brainGet;
    }

    static class TreeNode {

        private int troopersNeed;//所需士兵

        private int brainHave;//该房间拥有大脑数

        //由于不知道有几个子节点，所以就把子节点存在集合里
        private List<TreeNode> childList = new ArrayList<>();

        TreeNode(int bugs, int brainHave) {
            this.troopersNeed = bugs / 21 + 1;
            this.brainHave = brainHave;
        }

        public void addChild(int bugs, int brainHave) {
            TreeNode child = new TreeNode(bugs, brainHave);
            childList.add(child);
        }

        public List<TreeNode> getChildList() {
            return this.childList;
        }

        public int getTroopersNeed() {
            return troopersNeed;
        }

        public int getBrainHave() {
            return brainHave;
        }

    }
}