当前位置:网站首页>The maximum happiness of the party
The maximum happiness of the party
2022-07-05 23:02:00 【Bright morning light】
1、 subject
Employee information is defined as follows :
class Employee {
public int happy; // The happiness that this employee can bring
List<Employee> subordinates; // Which direct subordinates does this employee have
};
Every employee of the company meets Employee
Class description , The personnel structure of the whole company can be regarded as a standard 、 A multitree without rings . The root node of the tree is the only boss of the company . Every employee except the boss has a unique direct superior . Leaf nodes are grassroots employees without any subordinates (subordinates
The list is empty. ), In addition to grass-roots employees , Each employee has one or more direct subordinates .
The company is going to do party, You can decide which employees come to , Which employees don't come , The rules :
- If an employee comes , Then all the direct subordinates of this employee can't come ;
- The overall happiness of the queue is the accumulation of the happiness of all employees present ;
- Your goal is to maximize the overall happiness of the queue .
Given the root node of a multitree boss
, Please return the maximum happiness of the queue .
2、 analysis
Recursive routines using binary trees :
① The goal is : With X Get the maximum for the whole tree with roots happy value
② possibility :
1)X What happened here : hypothesis X Your direct subordinate is a,b,c, So happy value = X.happy + a No way max + b No way max + c No way max;
2)X The situation of not coming : Happiness value = 0 + max{a Come on ,a Not coming } + max{b Come on ,b Not coming } + max{c Come on ,c Not coming }
You can get , The information that needs to be obtained from the left and right subtrees is :① The largest node does not come happy value ;② The largest number of nodes happy value .
3、 Realization
C++ edition
/************************************************************************* > File Name: 042. The greatest pleasure of the party .cpp > Author: Maureen > Mail: [email protected] > Created Time: Two 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) {
}
};
// The current node is called cur
// Parameters up Express cur Whether your superior will come
// The meaning of function :
// up by true, Express cur The superior of determines the situation of coming ,cur The whole tree can provide the largest happy value
// up by false, Express cur Your superiors are not sure about the situation ,cur The whole tree can provide the largest happy value
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);
}
// Method 2 :
class Info {
public:
int no; // The root node does not come to the largest happy value
int yes; // The root node is the largest happy value
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 When you don't come , Children can come or not
no += max(nextInfo->no, nextInfo->yes);
//x when , Children cannot come
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 edition
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<>();
}
}
// Method 1 :
public static int maxHappy1(Employee boss) {
if (boss == null) {
return 0;
}
return process1(boss, false);
}
// The current node is called cur,
// up Express cur Whether your superior will come ,
// This function means :
// If up by true, It means that cur The superior has decided to come , Under the circumstances ,cur What is the maximum happiness value that the whole tree can provide ?
// If up by false, It means that cur The superior has decided not to come , Under the circumstances ,cur What is the maximum happiness value that the whole tree can provide ?
public static int process1(Employee cur, boolean up) {
if (up) {
// If cur If your superior comes ,cur No choice , Can only not come
int ans = 0;
for (Employee next : cur.nexts) {
ans += process1(next, false);
}
return ans;
} else {
// If cur If your superior doesn't come ,cur You can choose , You can come or not
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);
}
}
// Method 2 :
public static int maxHappy2(Employee head) {
Info allInfo = process(head);
return Math.max(allInfo.no, allInfo.yes); // The biggest benefit from the biggest boss , The biggest benefit of not coming to the biggest boss
}
public static class Info {
public int no; // The maximum when the root node does not come happy value
public int yes;// The maximum when the root node comes happy value
public Info(int n, int y) {
no = n;
yes = y;
}
}
public static Info process(Employee x) {
if (x == null) {
return new Info(0, 0); // Happiness value is 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 When you don't come , Children can come , Or not , Find the maximum of both
yes += nextInfo.no;// Children cannot come
}
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!");
}
}
边栏推荐
- 使用rewrite规则实现将所有到a域名的访问rewrite到b域名
- Fix the memory structure of JVM in one article
- d3dx9_ How to repair 31.dll_ d3dx9_ 31. Solution to missing DLL
- Alibaba Tianchi SQL training camp task4 learning notes
- Selenium+pytest automated test framework practice
- Unity Max and min constraint adjustment
- 抖音__ac_signature
- Nacos 的安装与服务的注册
- One article deals with the microstructure and instructions of class
- Global and Chinese markets of industrial pH meters 2022-2028: Research Report on technology, participants, trends, market size and share
猜你喜欢
查看网页最后修改时间方法以及原理简介
Common model making instructions
Usage Summary of scriptable object in unity
终于搞懂什么是动态规划的
Week 17 homework
My experience and summary of the new Zhongtai model
一文搞定JVM的内存结构
d3dx9_ What if 29.dll is missing? System missing d3dx9_ Solution of 29.dll file
30 optimization skills about mysql, super practical
Event trigger requirements of the function called by the event trigger
随机推荐
Hcip day 11 (BGP agreement)
Finally understand what dynamic planning is
Leecode learning notes
Thoroughly understand JVM class loading subsystem
How to quickly understand complex businesses and systematically think about problems?
Global and Chinese market of water treatment technology 2022-2028: Research Report on technology, participants, trends, market size and share
Event trigger requirements of the function called by the event trigger
Composition of interface
PLC编程基础之数据类型、变量声明、全局变量和I/O映射(CODESYS篇 )
Element operation and element waiting in Web Automation
30 optimization skills about mysql, super practical
[speech processing] speech signal denoising based on Matlab GUI Hanning window fir notch filter [including Matlab source code 1711]
The method and principle of viewing the last modification time of the web page
Unity Max and min constraint adjustment
链表之双指针(快慢指针,先后指针,首尾指针)
[secretly kill little buddy pytorch20 days] - [Day2] - [example of picture data modeling process]
Solve the problem of "no input file specified" when ThinkPHP starts
513. Find the value in the lower left corner of the tree
利用LNMP实现wordpress站点搭建
Realize reverse proxy client IP transparent transmission