最高效益
设有A，B，C，D，E五人从事J1，J2，J3，J4，J5五项工作，每人只能从事一项，他们的效益如下。
每人选择五项工作中的一项，在各种选择的组合中，找到效益最高的的一种组合输出。
【算法分析】
⒈用数组ｆ储存工作选择的方案；数组ｇ存放最优的工作选择方案；数组ｐ用于表示某项工作有没有被选择了。
⒉(1)选择ｐ(i)=0的第i项工作；
(2)判断效益是否高于max已记录的效益，若高于则更新ｇ数组及max的值。
⒊搜索策略: 回溯法（深度优先搜索dfs）。
1. #include<iostream> 2. #include<cstdio> 3. #include<iomanip> 4. using namespace std; 5. int data[6][6]={{0,0,0,0,0,0},{0,13,11,10,4,7}, 6. {0,13,10,10,8,5},{0,5,9,7,7,4}, 7. {0,15,12,10,11,5},{0,10,11,8,8,4}}; 8. int maxl=0,g[10],f[10]; 9. bool p[6]={0}; 10. int go(int step,int t)// step是第几个人，t是之前已得的效益 11. { 12. for(int i=1;i<=5;i++){ 13. if(!p[i]){ 14. f[step]=i; 15. p[i]=1; 16. t+=data[step][i]; 17. if(step<5) go(step+1,t); 18. else if(t>maxl){//保存最优效益下的工作选择方案 19. maxl=t; 20. for(int j=1;j<=5;j++) g[i]=f[i]; 21. } 22. t-=data[step][i];//回溯上一步 23. p[i]=0; 24. } 25. } 26. } 27. int main() 28. { 29. go(1,0); 30. for(int i=1;i<=5;i++) 31. cout<<char(64+i)<<":J"<<g[i]<<setw(3); 32. cout<<endl; 33. cout<<"supply:"<<maxl<<endl; 34. return 0; 35. }
选书
学校放寒假时，信息学竞赛辅导老师有A，B，C，D，E五本书，要分给参加培训的张、王、刘、孙、李五位同学，每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。
【算法分析】
可用穷举法，先不考虑“每人都满意” 这一条件，这样只剩“每人选一本且只能选一本”这一条件。在这个条件下，可行解就是五本书的所有全排列，一共有5！=120种。然后在120种可行解中一一删去不符合“每人都满意”的解，留下的就是本题的解答。
为了编程方便，设1，2，3，4，5分别表示这五本书。这五个数的一种全排列就是五本书的一种分发。例如54321就表示第5本书（即E）分给张，第4本书（即D）分给王，……，第1本书（即A）分给李。“喜爱书表”可以用二维数组来表示，1表示喜爱，0表示不喜爱。
算法设计：
S1：产生5个数字的一个全排列；
S2：检查是否符合“喜爱书表”的条件，如果符合就打印出来；
S3：检查是否所有的排列都产生了，如果没有产生完，则返回S1；
S4：结束。
改进算法：
在产生排列时，每增加一个数，就检查该数是否符合条件，不符合，就立刻换一个，符合条件后，再产生下一个数。因为从第I本书到第I+1本书的寻找过程是相同的，所以可以用回溯算法。算法设计如下：
1. int search(i) 2. { 3. for(j=1;j<=5;j++){ 4. if(第i个同学分到第j本书符合条件){ 5. 记录第i个数; 6. if(i==5) 打印一个解; 7. else search(i+1); 8. 删去第i个数; 9. } 10. } 11. }
1. #include<iostream> 2. #include<cstdio> 3. #include<iomanip> 4. using namespace std; 5. int book[6],c=0; 6. bool flag[6]; 7. bool like[6][6]={{0,0,0,0,0,0},{0,0,0,1,1,0},{0,1,1,0,0,1}, 8. {0,0,1,1,0,0},{0,0,0,0,1,0},{0,0,1,0,0,1}}; 9. void print() 10. { 11. c++; 12. cout<<"answer "<<c<<endl; 13. for(int i=1;i<=5;i++) cout<<i<<":"<<char(64+book[i]) <<endl; 14. } 15. int search(int i) 16. { 17. for(int j=1;j<=5;j++){ 18. if((!flag[j])&&like[i][j]){ 19. flag[j]=1; 20. book[i]=j; 21. if(i==5) print(); 22. else search(i+1); 23. flag[j]=0; 24. book[i]=0; 25. } 26. } 27. } 28. int main() 29. { 30. search(1); 31. return 0; 32. }
