员工的信息定义如下：
class Employee {
public int happy; //这名员工可以带来的快乐值
List<Employee> subordinates; //这名员工有哪些直接下级
};
公司的每个员工都符合 Employee 类的描述，整个公司的人员结构可以看做是一棵标准的、没有环的多叉树。树的根节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工（subordinates 列表为空），除基层员工外，每个员工都有一个或多个直接下级。
这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来，规则：
给定一棵多叉树的根节点 boss，请返回排队的最大快乐值。
使用二叉树的递归套路：
①目标：以 X 为根的整棵树获得最大 happy 值
②可能性：
1）X 来的情况：假设 X 的直接下级是 a，b，c，那么快乐值 = X.happy + a 不来的 max + b 不来的max + c不来的max；
2）X 不来的情况：快乐值 = 0 + max{a来，a不来} + max{b来，b不来} + max{c来，c不来}
整理可得，需要向左右子树获得信息是：①节点不来的最大happy值；②节点来的最大happy值。
/*************************************************************************
> File Name: 042.派对最大快乐值.cpp
> Author: Maureen
> Mail: Maureen@qq.com
> Created Time: 二 7/ 5 14:59:05 2022
************************************************************************/
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
class Employee {
public:
int happy;
vector<Employee*> subordinates;
Employee(int h) : happy(h) { }
};
//当前来到的节点叫做cur
//参数up表示cur的上级是否来
//函数的意义：
// up为true, 表示cur的上级确定要来的情况，cur 整棵树能提供的最大happy值
// up为false，表示cur的上级确定不来的情况，cur 整棵树能提供的最大happy值
int process1(Employee *cur, bool up) {
if (up) {
int ans = 0;
for (Employee *next : cur->subordinates) {
ans += process1(next, false);
}
return ans;
} else {
int p1 = cur->happy;
int p2 = 0;
for (Employee *next : cur->subordinates) {
p1 += process1(next, true);
p2 += process1(next, false);
}
return max(p1, p2);
}
}
int maxHappy1(Employee *boss) {
if (boss == nullptr)
return 0;
return process1(boss, false);
}
//方法二：
class Info {
public:
int no; //根节点不来的情况最大happy值
int yes; //根节点来的情况最大happy值
Info (int n, int y) : no(n), yes(y) {}
};
Info *process(Employee *x) {
if (x == nullptr) {
return new Info(0, 0);
}
int no = 0;
int yes = x->happy;
for (Employee *next : x->subordinates) {
Info *nextInfo = process(next);
//x不来的时候，子孩子可来可不来
no += max(nextInfo->no, nextInfo->yes);
//x来的时候，子孩子不能来
yes += nextInfo->no;
}
return new Info(no, yes);
}
int maxHappy2(Employee *boss) {
Info *allInfo = process(boss);
return max(allInfo->no, allInfo->yes);
}
//for test
void generateNexts(Employee *e, int level, int maxLevel, int maxNexts, int maxHappy) {
if (level > maxLevel) return ;
int nextsSize = rand() % (maxNexts + 1);
for (int i = 0; i < nextsSize; i++) {
Employee *next = new Employee(rand() % (maxHappy + 1));
e->subordinates.push_back(next);
generateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
}
}
Employee *generateBoss(int maxLevel, int maxNexts, int maxHappy) {
if ((rand() % 100 / (double)101) < 0.02) return nullptr;
Employee *boss = new Employee(rand() % (maxHappy + 1));
generateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
return boss;
}
int main() {
srand(time(0));
int maxLevel = 4;
int maxNexts = 7;
int maxHappy = 100;
int testTimes = 100000;
for (int i = 0; i < testTimes + 1; i++) {
Employee *boss = generateBoss(maxLevel, maxNexts, maxHappy);
if (maxHappy1(boss) != maxHappy2(boss)) {
cout << "Failed!" << endl;
return 0;
}
if (i && i % 1000 == 0) cout << i << " cases passed!" << endl;
}
cout << "Success！" << endl;
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class MaxHappy {
public static class Employee {
public int happy;
public List<Employee> nexts;
public Employee(int h) {
happy = h;
nexts = new ArrayList<>();
}
}
//方法一：
public static int maxHappy1(Employee boss) {
if (boss == null) {
return 0;
}
return process1(boss, false);
}
// 当前来到的节点叫cur，
// up表示cur的上级是否来，
// 该函数含义：
// 如果up为true，表示在cur上级已经确定来，的情况下，cur整棵树能够提供最大的快乐值是多少？
// 如果up为false，表示在cur上级已经确定不来，的情况下，cur整棵树能够提供最大的快乐值是多少？
public static int process1(Employee cur, boolean up) {
if (up) { // 如果cur的上级来的话，cur没得选，只能不来
int ans = 0;
for (Employee next : cur.nexts) {
ans += process1(next, false);
}
return ans;
} else { // 如果cur的上级不来的话，cur可以选，可以来也可以不来
int p1 = cur.happy;
int p2 = 0;
for (Employee next : cur.nexts) {
p1 += process1(next, true);
p2 += process1(next, false);
}
return Math.max(p1, p2);
}
}
//方法二：
public static int maxHappy2(Employee head) {
Info allInfo = process(head);
return Math.max(allInfo.no, allInfo.yes); //最大老板来的最大收益，和最大老板不来的最大收益
}
public static class Info {
public int no; //根节点不来的情况下的最大happy值
public int yes;//根节点来的情况下的最大happy值
public Info(int n, int y) {
no = n;
yes = y;
}
}
public static Info process(Employee x) {
if (x == null) {
return new Info(0, 0); //快乐值为0
}
int no = 0;
int yes = x.happy;
for (Employee next : x.nexts) {
Info nextInfo = process(next);
no += Math.max(nextInfo.no, nextInfo.yes); //x不来的时候，子孩子可以来，也可以不来，求二者的最大值
yes += nextInfo.no;//子孩子不能来
}
return new Info(no, yes);
}
// for test
public static Employee genarateBoss(int maxLevel, int maxNexts, int maxHappy) {
if (Math.random() < 0.02) {
return null;
}
Employee boss = new Employee((int) (Math.random() * (maxHappy + 1)));
genarateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
return boss;
}
// for test
public static void genarateNexts(Employee e, int level, int maxLevel, int maxNexts, int maxHappy) {
if (level > maxLevel) {
return;
}
int nextsSize = (int) (Math.random() * (maxNexts + 1));
for (int i = 0; i < nextsSize; i++) {
Employee next = new Employee((int) (Math.random() * (maxHappy + 1)));
e.nexts.add(next);
genarateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
}
}
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 = genarateBoss(maxLevel, maxNexts, maxHappy);
if (maxHappy1(boss) != maxHappy2(boss)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}