派对的最大快乐值

1、题目

员工的信息定义如下：

class Employee {
    
	public int happy; //这名员工可以带来的快乐值
	List<Employee> subordinates; //这名员工有哪些直接下级
};

公司的每个员工都符合 Employee 类的描述，整个公司的人员结构可以看做是一棵标准的、没有环的多叉树。树的根节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工（subordinates 列表为空），除基层员工外，每个员工都有一个或多个直接下级。

这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来，规则：

1. 如果某个员工来了，那么这个员工的所有直接下级都不能来；
2. 排队的整体快乐值是所有到场员工快乐值的累加；
3. 你的目标是让排队的整体快乐值尽量大。

给定一棵多叉树的根节点 boss，请返回排队的最大快乐值。

2、分析

使用二叉树的递归套路：
①目标：以 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值。

3、实现

C++ 版

/************************************************************************* > File Name: 042.派对最大快乐值.cpp > Author: Maureen > Mail: [email protected] > 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;
}

Java 版

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!");
	}   
}