派对的最大快乐值
员工信息的定义如下：
public static class Employee{ public int happy;//这名员工可以带来的快乐值 List<Employee> subordinates;//这名员工有哪些直接下级 }
公司的每个员工都符合Employee类的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级。
这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则:
- 如果某个员工来了，那么这个员工的所有直接下级都不能来
- 派对的整体快乐值是所有到场员工快乐值的累加
- 你的目标是让派对的整体快乐值尽量大
给定一棵多叉树的头节点boss，请返回派对的最大快乐值。
第一种可能性：X结点来（就是给X结点发请柬），假设X有三个直接下级a,b,c，如果给X发请柬的话，快乐值就是：
X自己的快乐值
+
a不来情况下整颗子树的快乐值
+
b不来情况下整颗子树的快乐值
+
c不来情况下整颗子树的快乐值，
因为a,b,c不能来。
第二种可能性：X结点不来（就是不给X发请柬），假设X有三个直接下级a,b,c，如果不给X发请柬的话，快乐值就是：
X自己的快乐值0
+
max{a来的情况下整颗树的快乐值，a不来的情况下整棵树的快乐值}
+
max{b来的情况下整颗树的快乐值，b不来的情况下整棵树的快乐值}
+
max{c来的情况下整颗树的快乐值，c不来的情况下整棵树的快乐值}
所以任何子树都需要返回的信息就是：
- 头结点来的情况下，整颗子树的快乐值是多少
- 头结点不来的情况下，整颗子树的快乐值是多少
public static class Info{ public int yes;// 对于任何子树都要返回 头结点来的情况下，整颗子树的快乐值 public int no;// 对于任何子树都要返回 头结点不来的情况下，整颗子树的快乐值 public Info(int y,int n) { yes=y; no=n; } }
完整代码：
package com.harrison.class08; import java.util.ArrayList; import java.util.List; public class Code04_MaxHappy { public static class Employee{ public int happy;//这名员工可以带来的快乐值 List<Employee> nexts;//这名员工有哪些直接下级 public Employee(int h) { happy = h; nexts = new ArrayList<>(); } } public static class Info{ public int yes;// 对于任何子树都要返回 头结点来的情况下，整颗子树的快乐值 public int no;// 对于任何子树都要返回 头结点不来的情况下，整颗子树的快乐值 public Info(int y,int n) { yes=y; no=n; } } public static Info process1(Employee x) { if(x==null) { return new Info(0, 0); } // X来的情况下先直接获得X的快乐值 int yes=x.happy; // X不来情况下，快乐值就是0 int no=0; // X来：累加上X的直接下级不来的情况下的快乐值 // X不来：累加上X的直接下级来的情况和不来的情况 的 最大值 for(Employee next:x.nexts) { Info nextInfo=process1(next); yes+=nextInfo.no; no+=Math.max(nextInfo.yes, nextInfo.no); } return new Info(yes, no); } public static int maxHappy1(Employee head) { Info allInfo=process1(head); return Math.max(allInfo.yes, allInfo.no); } // 当前来到的节点叫cur， // up表示cur的上级是否来， // 该函数含义： // 如果up为true，表示在cur上级已经确定来，的情况下，cur整棵树能够提供最大的快乐值是多少？ // 如果up为false，表示在cur上级已经确定不来，的情况下，cur整棵树能够提供最大的快乐值是多少？ public static int process2(Employee cur, boolean up) { if (up) { // 如果cur的上级来的话，cur没得选，只能不来 int ans = 0; for (Employee next : cur.nexts) { ans += process2(next, false); } return ans; } else { // 如果cur的上级不来的话，cur可以选，可以来也可以不来 int p1 = cur.happy; int p2 = 0; for (Employee next : cur.nexts) { p1 += process2(next, true); p2 += process2(next, false); } return Math.max(p1, p2); } } public static int maxHappy2(Employee boss) { if (boss == null) { return 0; } return process2(boss, false); } public static void generateNexts(Employee e,int level,int maxLevel,int maxNexts,int maxHappy) { if(level>maxLevel) { return ; } int nextSize=(int)(Math.random()*(maxNexts+1)); for(int i=0; i<nextSize; i++) { Employee next=new Employee((int)(Math.random()*(maxHappy+1))); e.nexts.add(next); generateNexts(next, level+1, maxLevel, maxNexts, maxHappy); } } public static Employee generateBoss(int maxLevel,int maxNexts,int maxHappy) { if(Math.random()<0.02) { return null; } Employee boss=new Employee((int)(Math.random()*(maxHappy+1))); generateNexts(boss, 1, maxLevel, maxNexts, maxHappy); return boss; } public static void main(String[] args) { int maxLevel = 4; int maxNexts = 7; int maxHappy = 100; int testTimes = 100000; for (int i = 0; i < testTimes; i++) { Employee boss = generateBoss(maxLevel, maxNexts, maxHappy); if (maxHappy1(boss) != maxHappy2(boss)) { System.out.println("Oops!"); } } System.out.println("finish!"); } }
