派對最大快樂值問題

作者：Grey

原文地址：

題目描述

員工資訊的定義如下:

    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){}

表示當前員工來或者不來的最大快樂值是多少。

接下來是整理可能性

當前員工參加，下屬員工都不可以參加
當前員工不參加，下屬員工可以參加也可以不參加

依據上述可能性，遞迴函數實現如下（核心程式碼見註釋說明）

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

演演算法和資料結構筆記

派對最大快樂值問題

派對最大快樂值問題

更多