派对的最大快乐值

2023-12-05 13:12

文章标签 最大快乐派对

本文主要是介绍派对的最大快乐值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

与其明天开始，不如现在行动！

文章目录

- - 派对的最大快乐值
💎总结

派对的最大快乐值

题目

员工信息的定义如下：

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

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

派对的最大快乐值

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

1.如果某个员工来了，那么这个员工的所有直接下级都不能来

2.派对的整体快乐值是所有到场员工快乐值的累加

3.你的目标是让派对的整体快乐值尽量大给定一棵多叉树的头节点boss，请返回派对的最大快乐值

员工举例
在这里插入图片描述

代码实现

public class MaxHappy {public static class Employee{public int happy;List<Employee> next;public Employee(int happy){this.happy = happy;next = new ArrayList<>();}}public static class Info {public int yes;public int no;public Info(int yes, int no) {this.yes = yes;this.no = no;}}public static int getMaxHappy(Employee boss) {if (boss == null) {return 0;}Info allHappy = process(boss);return Math.max(allHappy.yes, allHappy.no);}private static Info process(Employee node) {// 基层员工的信息if (node.next.isEmpty()) {return new Info(node.happy, 0);}int yes = node.happy;int no = 0;for (Employee next : node.next) {// 递归Info nextInfo = process(next);// 父节点去的话，子节点都不去 的最大快乐值yes += nextInfo.no;// 父节点不去，子节点在去或不去的快乐值中选最大的no += Math.max(nextInfo.yes, nextInfo.no);}return new Info(yes, no);}// 测试public static void main(String[] args) {Employee boss = new Employee(10);Employee employee0 = new Employee(10);Employee employee1 = new Employee(5);Employee employee2 = new Employee(6);Employee employee3 = new Employee(7);Employee employee4 = new Employee(3);Employee employee5 = new Employee(2);Employee employee6 = new Employee(4);Employee employee7 = new Employee(1);Employee employee8 = new Employee(2);Employee employee9 = new Employee(3);boss.next.add(employee0);employee0.next.add(employee1);employee0.next.add(employee2);employee0.next.add(employee3);employee1.next.add(employee4);employee2.next.add(employee5);employee3.next.add(employee6);employee4.next.add(employee7);employee5.next.add(employee8);employee6.next.add(employee9);System.out.println(getMaxHappy(boss));}
}