公司聚会计划

公司内部结构关系是层次化的,即员工按主管—下属关系构成一棵树,根节点为公司主席。人事部按“宴会交际能力”给每个员工打分,分值为实数。
Stewart教授是一家公司总裁的顾问,这家公司正在计划一个公司的聚会。这个公司有一个层次式的结构;也就是,管理关系形成一颗以总裁为根的树。人事部门按每个员工喜欢聚会的程度来排名,排名是一个实数。为了使每个参加聚会者都喜欢这个聚会,总裁不希望一个雇员和她的直接上司同时参加。

Stewart教授面对一颗描述公司结构的树,使用了左孩子右兄弟描述法。树中每个节点除了包含指针,还包含雇员的名字以及雇员喜欢聚会的排名。描述一个算法,它生成一张客人列表,使得客人喜欢聚会的程度的总和最大。分析你的算法的执行时间。

最大喜欢程度和?

动态规划原理:
1、重叠子问题:
该问题会对某个领导的下属反复求解。

2、最优子结构
公司聚会有最佳方案,构成最优子结构

状态转移函数:

$people(0)=\sum max(confirm(i,0),confirm(i,1))$
$people(1)=likevalue+\sum confirm(i,0)$
$result=max(confirm(root,0),confirm(root,1))$

邻接矩阵求解

company_party_array.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>

#define MAXNUM 20

//使用有向图的邻接矩阵来表示
bool party_graph[MAXNUM][MAXNUM];
int solution[MAXNUM][2]; //用来存储解决方案,solution[i][0]表示不被选中
//solution[i][1]表示被选中
int likevalue[MAXNUM]; //表示对party的热衷程度

int how_many_member;

int id;
int how_many_branch,branch_id;

int max(int a,int b)
{
return a>b?a:b;
}

int confirm(int id,int status) //递归求解方案
{
int result;
if(solution[id][status]!=-1)
return solution[id][status];
if(status==0)
{
result=0;
//表示这个id不参加聚会
for(int i=0;i<how_many_member;i++) //遍历这个id的边,即邻接链表
{
if(party_graph[id][i])
result+=max(confirm(i,0),confirm(i,1));
}
solution[id][status]=result;
return result;
}
else
{
result=likevalue[id];
for(int i=0;i<how_many_member;i++)
{
if(party_graph[id][i])
result+=confirm(i,0);
}
solution[id][status]=result;
return result;
}
}

company_party_array.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include "company_party_array.h"
#include <string.h>

using namespace std;

int main()
{

//Initialize:对数组的值进行初始化
for(int i=0;i<MAXNUM;i++)
{
for(int j=0;j<2;j++)
solution[i][j]=-1;
}
cout<<"Input the number of members who join the party: "<<endl;
cin>>how_many_member;

cout<<"Input the like value of members: "<<endl;
for(int i=0;i<how_many_member;i++)
cin>>likevalue[i];



for(int i=0;i<how_many_member;i++)
{
cout<<"Input member id and how many branch it has: "<<endl;
cin>>id>>how_many_branch; //输入每个人的编号和下属的个数
cout<<"branch id: "<<endl;
for(int j=0;j<how_many_branch;j++)
{
cin>>branch_id; //输入下属员工的id
party_graph[id][branch_id]=true;
}
}
//初始化完成
int root=0;
int result=confirm(root,0);
memset(solution,-1,sizeof(solution));
//注意使用这种方法,对数组中的值进行赋值

result=max(result,confirm(root,1));
cout<<result<<endl;
return 0;
}

左孩子右兄弟树求解

用辅助队列完成

特别说明:用辅助队列,使用标准库比较安全

1
queue<CSTree> helpqueue;

用g++编译的时候,在最新的版本中,用malloc分配内存会出现错误

1
CSTree child_node=temp->firstChild=new CSNode;

使用new来分配内存

CSTree.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
#include <iostream>
#include <cstdlib>
#include <queue>
#include <string.h>

#define Wrong 'W'

using namespace std;

typedef struct CSNode
{
int data;
int status;
struct CSNode *firstChild;
struct CSNode *nextsibling;
struct CSNode *parent;
}CSNode,*CSTree;

int InitTree(CSTree &T)
{
T=NULL;
return true;
}

int CreateTree(CSTree &T)
{
queue<CSTree> helpqueue;
int buffchild[10]={0};
int child_num;

cout<<"Input root of the tree: if empty, enter -1: "<<endl;
cin>>buffchild[0];

if(buffchild[0]!=-1)
{
T=new CSNode;
T->status=-1;
T->data=buffchild[0];
T->nextsibling=NULL;
helpqueue.push(T); //根结点入队,只存储根节点

while(!helpqueue.empty())
{
CSTree temp=helpqueue.front();
helpqueue.pop();

cout<<"Input the child number of "<<temp->data<<" if child number is 0, please enter '0'"<<endl;
cin>>child_num;

cout<<"Input the child data of "<<temp->data<<" ,if it has no child , enter -1"<<endl;
for(int i=0;i<child_num;i++)
cin>>buffchild[i];

if(child_num!=0)
{
CSTree child_node=temp->firstChild=new CSNode;
child_node->status=-1;
child_node->data=buffchild[0];

helpqueue.push(child_node); //第一个孩子入队列

for(int i=1;i<child_num;i++)
{
child_node->nextsibling=new CSNode;
child_node->nextsibling->data=buffchild[i];

helpqueue.push(child_node->nextsibling);
child_node=child_node->nextsibling; //指向刚刚入队的孩子
}
child_node->nextsibling=NULL;
}
else
temp->firstChild=NULL;
}
}
else
T=NULL;
return true;
}

void DestroyTree(CSTree &T)
{
if(T)
{
if(T->firstChild)
DestroyTree(T->firstChild);
if(T->nextsibling)
DestroyTree(T->nextsibling);
free(T);
T=NULL;
}
}

void ClearTree(CSTree &T)
{
DestroyTree(T);
}

bool TreeEmpty(CSTree &T)
{
if(T)
return true;
else
return false;
}

int TreeDepth(CSTree &T)
{
if(!T)
return 0;
if(!T->firstChild)
return 1;
CSTree child_ptr;
int depth, max=0;

for(child_ptr=T->firstChild;child_ptr;child_ptr=child_ptr->nextsibling)
{
depth=TreeDepth(child_ptr);
if(depth>max)
max=depth;
}
return max+1;
}

int Root(CSTree &T,int cur_node)
{
if(T)
return T->data;
return 0;
}

CSNode *FindNode(CSTree &T,int cur_node)
{
queue<CSTree> Q;
if(T)
{
Q.push(T);
while(!Q.empty())
{
CSTree tmp_node=Q.front();
Q.pop();

if(tmp_node->data==cur_node)
return tmp_node;
if(tmp_node->firstChild)
Q.push(tmp_node->firstChild);
if(tmp_node->nextsibling)
Q.push(tmp_node->nextsibling);
}
}
return NULL;
}

bool Assign(CSTree &T,int cur_node,int value) //进行赋值操作
{
if(!T)
return false;
CSNode *find_cur_node=FindNode(T,cur_node);
if(!find_cur_node)
return false;
find_cur_node->data=value;
return true;
}

CSNode *parent(CSTree &T,int cur_value)
{
queue<CSTree> Q;
if(T)
{
if(T->data==cur_value)
return NULL;
Q.push(T);
while(!Q.empty())
{
CSTree cur_node=Q.front();
Q.pop();

CSTree parent_ptr=cur_node;
if(cur_node->firstChild)
{
if(cur_node->firstChild->data==cur_value)
return parent_ptr;
Q.push(cur_node->firstChild);

CSTree brotherptr=cur_node->firstChild->nextsibling;
while(brotherptr)
{
if(brotherptr->data==cur_value)
return parent_ptr;
Q.push(brotherptr);
brotherptr=brotherptr->nextsibling;
}
}
}
}
return NULL;
}

int leftchild(CSTree &T,int cur_node)
{
CSNode *node=FindNode(T,cur_node);
if(node)
{
if(node->firstChild)
return node->firstChild->data;
}
return Wrong;
}

int rightsibling(CSTree &T,int cur_node)
{
CSNode *node=FindNode(T,cur_node);
if(node)
{
if(node->nextsibling)
return node->nextsibling->data;
}
return Wrong;
}

bool LevelOrderTraverse(CSTree T)
{
queue<CSTree> Q;

if(T)
{
cout<<T->data<<" ";
Q.push(T);
while(!Q.empty())
{
CSTree cur_node,child_node;
cur_node=Q.front();
Q.pop();

child_node=cur_node->firstChild;
while(child_node)
{
cout<<child_node->data<<" ";
Q.push(child_node);
child_node=child_node->nextsibling;
}
}
return true;
}
return false;
}

void recurse_Traverse(CSTree T)
{
if(T)
{
T->status=-1;
cout<<T->data<<" "<<T->status<<" ";
recurse_Traverse(T->firstChild);
recurse_Traverse(T->nextsibling);
}
}

void refresh_tree(CSTree &T)
{
if(T)
{
T->status=-1;
refresh_tree(T->firstChild);
refresh_tree(T->nextsibling);
}
}

void recurse_createtree(CSTree T)
{
int child_number;
cout<<"Input the child number of "<<T->data<<" if it has no child, input 0 "<<endl;
cin>>child_number;

if(child_number==0)
{
T->firstChild=NULL;
}
else
{
CSTree child,ptr;
int child_data;
child=new CSNode;
child->status=-1;

cout<<"Input the data of the child node : "<<endl;
cin>>child_data;

child->data=child_data;

T->firstChild=child;
ptr=child;

for(int i=1;i<child_number;i++)
{
CSTree brother=new CSNode;
brother->status=-1;

int brother_data;

cout<<"Input the data of the child node: "<<endl;
cin>>brother_data;
brother->data=brother_data;

ptr->nextsibling=brother;
ptr=ptr->nextsibling;
}
ptr->nextsibling=NULL;

for(CSTree p=T->firstChild;p;p=p->nextsibling)
recurse_createtree(p);

}
}


void depth_traverse(CSTree &T)
{
if(T)
{
T->status=-1;
cout<<T->data<<" "<<T->status<<" ";

for(CSTree p=T->firstChild;p;p=p->nextsibling)
depth_traverse(p);
}
}

company_party.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include "CSTree.h"


int max(int a,int b)
{
return a>b?a:b;
}

int confirm(CSTree &T,int flag)
{
int result;
if(T->status!=-1)
return T->status;
if(flag==1)
{
result=T->data;
for(CSTree p=T->firstChild;p!=NULL;p=p->nextsibling)
{
result+=confirm(p,0);
}
T->status=result;
return result;
}
else
{
result=0;
int maxnum;
for(CSTree p=T->firstChild;p;p=p->nextsibling)
{
maxnum=confirm(p,0);
refresh_tree(p); //注意在求max的时候,洗刷status的值
maxnum=max(maxnum,confirm(p,1));
result+=maxnum;
}
T->status=result;
return result;
}
}

int main()
{
CSTree T;
CreateTree(T);

cout<<"Level order Traverse: "<<endl;
LevelOrderTraverse(T);
cout<<endl;
recurse_Traverse(T);
cout<<endl;

int result=confirm(T,1);
cout<<result<<endl;
refresh_tree(T);
cout<<endl;
result=max(result,confirm(T,0));
cout<<result;
cout<<endl;

cout<<"recurse mathod:"<<endl;

CSTree Recur_T;
int root_data;
Recur_T=new CSNode;
Recur_T->status=-1;
cout<<"Input the data of root : "<<endl;
cin>>root_data;
Recur_T->data=root_data;

recurse_createtree(Recur_T);
cout<<"Level order Traverse: "<<endl;
LevelOrderTraverse(Recur_T);
cout<<endl;
depth_traverse(Recur_T);
cout<<endl;
}

递归建立左孩子右兄弟树的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void recurse_createtree(CSTree T)
{
int child_number;
cout<<"Input the child number of "<<T->data<<" if it has no child, input 0 "<<endl;
cin>>child_number;

if(child_number==0)
{
T->firstChild=NULL;
}
else
{
CSTree child,ptr;
int child_data;
child=new CSNode;
child->status=-1;

cout<<"Input the data of the child node : "<<endl;
cin>>child_data;

child->data=child_data;

T->firstChild=child;
ptr=child;

for(int i=1;i<child_number;i++)
{
CSTree brother=new CSNode;
brother->status=-1;

int brother_data;

cout<<"Input the data of the child node: "<<endl;
cin>>brother_data;
brother->data=brother_data;

ptr->nextsibling=brother;
ptr=ptr->nextsibling;
}
ptr->nextsibling=NULL;

for(CSTree p=T->firstChild;p;p=p->nextsibling)
recurse_createtree(p);

}
}

实现结果

非递归建树(使用辅助队列):

01

递归建树的过程:
仅用于测试:

02

特别注意:在用树实现递归的时候,算完一次confirm()之后,要使用refresh_tree把树刷新一遍,去掉第一次计算的痕迹