公司內部結構關系是層次化的，即員工按主管–下屬關系構成一棵樹，根節點為公司主席。人事部按“宴會交際能力”給每個員工打分，分值為實數。
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

#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

#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; //輸入下屬員工的idparty_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; }

左孩子右兄弟樹求解

用輔助隊列完成

LinkQueue.h

#include <iostream> #include <ctime> #include <cmath> #include "CSTree.h" #include <stdlib.h>using namespace std;#define MAXSIZE 20 //存儲空間初始分配量bool visit(QNodePtr c) {cout<<c->data;return true; }//構造一個空隊列 int InitQueue(LinkQueue *Q) {Q->front=Q->rear=(QNodePtr)malloc(sizeof(QNode));if(!Q->front){cout<<"overfolow";exit(OVERFLOW);}Q->front->next=NULL;return true; }//銷毀隊列，完成之后Q->front==Q->rear==NULL,均為空指針 bool DestroyQueue(LinkQueue *Q) {while(Q->front){Q->rear=Q->front->next;free(Q->front);Q->front=Q->rear;}return true; }//將Q清為空隊列 bool ClearQueue(LinkQueue *Q) {QNodePtr p,q;Q->rear=Q->front;p=Q->front->next;Q->front->next=NULL;while(p){q=p;p=p->next;free(q);}return true; }bool QueueEmpty(LinkQueue Q) {if(Q.front==Q.rear)return true;elsereturn false; }//求隊列的長度 int QueueLength(LinkQueue Q) {int count=0;QNodePtr p=Q.front;while(Q.rear!=p){count++;p=p->next;}return count; }bool GetHead(LinkQueue Q,QElemType *element) {QNodePtr p;if(Q.front==Q.rear)return false;p=Q.front->next;*element=p->data;return true; }//插入元素e為Q的新的隊尾元素 bool Enqueue(LinkQueue *Q,QElemType element) {QNodePtr s=(QNodePtr)malloc(sizeof(QNode));if(!s)exit(OVERFLOW);s->data=element;s->next=NULL;Q->rear->next=s;Q->rear=s;return true; }bool Dequeue(LinkQueue *Q,QElemType *element) {QNodePtr p;if(Q->front==Q->rear)return false;p=Q->front->next; //將要刪除的隊頭節點暫時存給p*element=p->data;//重置隊頭Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;free(p);return true; }bool QueueTraverse(LinkQueue Q) {QNodePtr p;p=Q.front->next;while(p){visit(p);p=p->next;}cout<<endl;return true; }

CSTree.h

#include <iostream> #include <string.h> #include <stdlib.h>#define Wrong 'W'using namespace std;typedef int Elemtype;typedef struct CSNode {Elemtype data;int status;struct CSNode *firstChild;struct CSNode *nextsibling; }CSNode,*CSTree;typedef CSTree QElemType;typedef struct QNode {QElemType data;struct QNode *next; }QNode,*QNodePtr;typedef struct {QNodePtr front,rear;//隊頭，隊尾指針 }LinkQueue;int InitQueue(LinkQueue *Q); bool DestroyQueue(LinkQueue *Q); bool visit(QNodePtr c); bool ClearQueue(LinkQueue *Q); bool QueueEmpty(LinkQueue Q); int QueueLength(LinkQueue Q); bool GetHead(LinkQueue Q,QElemType *element); bool Enqueue(LinkQueue *Q,QElemType element); bool Dequeue(LinkQueue *Q,QElemType *element); bool QueueTraverse(LinkQueue Q);int CreateTree(CSTree &T) {LinkQueue helpQueue;InitQueue(&helpQueue);int buffchild[10];//用來存放孩子們的緩存int child_num;memset(buffchild,0,10);cout<<"Input root of the tree: if empty,enter -1: "<<endl;cin>>buffchild[0];if(buffchild[0]!=-1){T=(CSTree)malloc(sizeof(CSTree));T->status=-1;if(!T)exit(OVERFLOW);T->data=buffchild[0];T->nextsibling=NULL;Enqueue(&helpQueue,T); //根節點入隊，只存儲根節點while(!QueueEmpty(helpQueue)){QElemType temp;Dequeue(&helpQueue,&temp);//根節點出隊cout<<"Input the child number of "<<temp->data<<" if child number is 0, please enter '0'"<<endl;cin>>child_num;cout<<"Input the data of child "<<temp->data<<" ,if has no child ,enter -1"<<endl;for(int i=0;i<child_num;i++)cin>>buffchild[i];if(child_num!=0) //表示有孩子，根為temp{CSTree child_node;child_node=(CSTree)malloc(sizeof(CSTree)); //開辟孩子節點空間child_node->status=-1;if(!child_node)exit(OVERFLOW);child_node->data=buffchild[0];//建立此時的根temp和child_node的孩子關系temp->firstChild=child_node;Enqueue(&helpQueue,child_node); //第一個孩子入隊CSTree child_ptr=child_node;for(size_t i=1;i<child_num;i++){child_node=(CSTree)malloc(sizeof(CSTree));child_node->status=-1;if(!child_node)exit(OVERFLOW);child_node->data=buffchild[i];child_ptr->nextsibling=child_node;Enqueue(&helpQueue,child_node);child_ptr=child_node; //指向剛入隊的孩子}child_ptr->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;elsereturn 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; }Elemtype Root(CSTree &T) {if(T)return T->data;return 0; }CSNode* FindNode(CSTree &T,Elemtype cur_node) {LinkQueue Q;InitQueue(&Q); //構造一個空隊列if(T){Enqueue(&Q,T); //根節點入隊while(!QueueEmpty(Q)){QElemType tmp_node;Dequeue(&Q,&tmp_node);if(tmp_node->data==cur_node)return tmp_node;if(tmp_node->firstChild)Enqueue(&Q,tmp_node->firstChild);if(tmp_node->nextsibling)Enqueue(&Q,tmp_node->nextsibling); }}return NULL; }bool Assign(CSTree &T,Elemtype cur_node,Elemtype 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,Elemtype cur_value) {LinkQueue Q;InitQueue(&Q);if(T){if(T->data==cur_value)return NULL; //根節點無雙親Enqueue(&Q,T);while(!QueueEmpty(Q)){QElemType cur_node;Dequeue(&Q,&cur_node); //當前節點可能作為根節點，為cur_nodeQElemType parent_ptr=cur_node; //提示剛出隊的元素if(cur_node->firstChild){if(cur_node->firstChild->data==cur_value)return parent_ptr;Enqueue(&Q,cur_node->firstChild);QElemType brotherPtr=cur_node->firstChild->nextsibling;//指向孩子的兄弟節點while(brotherPtr){if(brotherPtr->data==cur_value)return parent_ptr;Enqueue(&Q,brotherPtr);brotherPtr=brotherPtr->nextsibling;}}}}return NULL; }Elemtype Leftchild(CSTree &T,Elemtype cur_node) {CSNode* node;node=FindNode(T,cur_node);if(node){if(node->firstChild)return node->firstChild->data;}return Wrong; }Elemtype Rightsibling(CSTree &T,Elemtype cur_node) {CSNode* node;node=FindNode(T,cur_node);if(node){if(node->nextsibling){return node->nextsibling->data;}}return Wrong; }bool LevelOrderTraverse(CSTree &T) {//層序遍歷LinkQueue Q;InitQueue(&Q);if(T){cout<<T->data<<" ";Enqueue(&Q,T); //根節點排隊while(!QueueEmpty(Q)){QElemType cur_node,child_node;Dequeue(&Q,&cur_node); //當前根節點出隊child_node=cur_node->firstChild;while(child_node){cout<<child_node->data<<" ";Enqueue(&Q,child_node);child_node=child_node->nextsibling;}}return true;}return false; }bool 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);} }bool 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;return true;}else{CSTree child,ptr;int child_data;child=(CSTree)malloc(sizeof(CSTree));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;int brother_data;brother=(CSTree)malloc(sizeof(CSTree));brother->status=-1;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);}return true;} }bool 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

#include "LinkQueue.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=(CSTree)malloc(sizeof(CSTree));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; }

遞歸版本

CSTree.h

#include <iostream> #include <string.h> #include <stdlib.h>#define Wrong 'W'using namespace std;typedef int Elemtype;typedef struct CSNode {Elemtype data;int status;struct CSNode *firstChild;struct CSNode *nextsibling; }CSNode,*CSTree;bool 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;return true;}else{CSTree child,ptr;int child_data;child=(CSTree)malloc(sizeof(CSTree));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;int brother_data;brother=(CSTree)malloc(sizeof(CSTree));brother->status=-1;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);}return true;} }bool 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

#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() {cout<<"recurse mathod:"<<endl;CSTree Recur_T;int root_data;Recur_T=(CSTree)malloc(sizeof(CSTree));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; }

實現結果

非遞歸算法：

遞歸算法：
僅用于測試：

特別注意：在用樹實現遞歸的時候，算完一次confirm()之后，要使用refresh_tree把樹刷新一遍，去掉第一次計算的痕跡

總結

以上是生活随笔為你收集整理的公司聚会计划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。