派对最大快乐值问题

作者：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();
    }
}

更多

算法和数据结构笔记