派对最大快乐值问题

派对最大快乐值问题

作者：Grey

原文地址：

博客园：派对最大快乐值问题

CSDN：派对最大快乐值问题

题目描述

员工信息的定义如下:

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

公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。

叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级。这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来，

规则：

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

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

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

题目链接: 没有上司的舞会

本题可以用二叉树的递归套路方法来解，

定义如下数据结构

    public static class Info {         public int yes;         public int no;           public Info(int yes, int no) {             this.yes = yes;             this.no = no;         }     } 

其中：

yes变量表示当前员工来的话，最大快乐值是多少。

no变量表示当前不来的话，最大快乐值是多少。

定义递归函数

public static Info p(Employee boss){} 

表示当前员工来或者不来的最大快乐值是多少。

接下来是整理可能性

1. 当前员工参加，下属员工都不可以参加

2. 当前员工不参加，下属员工可以参加也可以不参加

依据上述可能性，递归函数实现如下（核心代码见注释说明）

    public static Info p(Employee boss) {         if (boss.subordinates == null || boss.subordinates.isEmpty()) {             return new Info(boss.happy, 0);         }         List<Employee> subordinates = boss.subordinates;         int yes = boss.happy;         int no = 0;         for (Employee e : subordinates) {             Info info = p(e);             // boss参加了,下属可以不参加             yes += info.no;             // boss没有参加,下属可以参加也可以不参加             no += Math.max(info.yes, info.no);         }         return new Info(yes, no);     } 

主函数直接调用

Info info = p(boss); // 当前员工来或者不来的最大值 return Math.max(info.yes, info.no); 

完整代码见

import java.util.*;   public class Main {     public static class Employee {         public int happy;         public List<Employee> subordinates;           public Employee(int happy) {             this.happy = happy;             this.subordinates = 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 maxHappy(Employee boss) {         if (boss == null) {             return 0;         }         Info info = p(boss);         return Math.max(info.yes, info.no);     }       public static Info p(Employee boss) {         if (boss.subordinates == null || boss.subordinates.isEmpty()) {             return new Info(boss.happy, 0);         }         List<Employee> subordinates = boss.subordinates;         int yes = boss.happy;         int no = 0;         for (Employee e : subordinates) {             Info info = p(e);             // boss参加了,下属可以不参加             yes += info.no;             // boss没有参加,下属可以参加也可以不参加             no += Math.max(info.yes, info.no);         }         return new Info(yes, no);     }     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int count = sc.nextInt();         Map<Integer, Employee> map = new HashMap<>();         List<Integer> tmp = new LinkedList<>();         for (int i = 1; i <= count; i++) {             int happy = sc.nextInt();             map.put(i, new Employee(happy));             tmp.add(i);         }         Set<Integer> notBoss = new HashSet<>();         for (int i = 1; i <= count; i++) {             if (i != count) {                 int child = sc.nextInt();                 int father = sc.nextInt();                 notBoss.add(child);                 Employee f = map.get(father);                 Employee c = map.get(child);                 f.subordinates.add(c);             }         }         int bossIndex = 0;         for (Integer it : tmp) {             if (!notBoss.contains(it)) {                 bossIndex = it;                 break;             }         }         Employee boss = map.get(bossIndex);         System.out.println(maxHappy(boss));         sc.close();     } } 

更多

算法和数据结构笔记