精品文档
本科实验报告
课程名称： 算法设计与分析
实验项目： 递归与分治算法
实验地点： 计算机系实验楼110
专业班级： 物联网1601 学号： 2016002105
学生姓名： 俞梦真
指导教师： 郝晓丽
2018年 05月 04 日
实验一 递归与分治算法
1.1 实验目的与要求
1．进一步熟悉C/C++语言的集成开发环境；
2．通过本实验加深对递归与分治策略的理解和运用。
1.2 实验课时
2学时
1.3 实验原理
分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。
需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。
1.4 实验题目
1．上机题目：格雷码构造问题
Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意 QUOTE n n构造相应的Gray码（分治、减治、变治皆可）。
对于给定的正整数n，格雷码为满足如下条件的一个编码序列。
（1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。
（2）序列中无相同的编码。
（3）序列中位置相邻的两个编码恰有一位不同。
2．设计思想：
根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。
3．代码设计：
#include<cstdio>
#include<iostream>
#include <cstring>
#include<vector>
using namespace std;
//求格雷码 递推式子：G(n-1)=B(n-1) G(i)=B(i+1)异或B(i) (0<i<n-2)
//输出n位GRad码---普通方法
vector<string> My_grad;
void get_grad(int n)
{
//cout<<1<<endl;
My_grad.push_back("0");
My_grad.push_back("1");//前面两位
if(n>1)
{
//cout<<1<<endl;
for(int i=2;i<=n;i++)
{
vector<string> tmp;
for(int j=0;j<My_grad.size();j++)
{
tmp.push_back(My_grad[j]);
string s="0";
s+=tmp[j];
My_grad[j]=s;//
}
//翻转
for(int j=tmp.size()-1;j>=0;j--)
{
string s="1";
s+=tmp[j];
My_grad.push_back(s);
}
}
}
}
int main()
{
int n;
while(cin>>n)
{
get_grad(n);
for(int i=0;i<My_grad.size();i++)
cout<<My_grad[i]<<endl;
My_grad.clear();
}
return 0;
}
运行结果：
1.5 思考题
（1）递归的关键问题在哪里？
答：
1.递归式，就是如何将原问题划分成子问题。
2.递归出口，递归终止的条件，即最小子问题的求解，可以允许多个出口。
3.界函数，问题规模变化的函数，它保证递归的规模向出口条件靠拢（2）递归与非递归之间如何实现程序的转换？
（3）分析二分查找和快速排序中使用的分治思想。
答：
1．一般根据是否需要回朔可以把递归分成简单递归和复杂递归，简单递归一般就是根据递归式来找出递推公式（这也就引申出分治思想和动态规划）。
2．复杂递归一般就是模拟系统处理递归的机制，使用栈或队列等数据结构保存回朔点来求解。
（4）分析二次取中法和锦标赛算法中的分治思想。
二次取中法：使用快速排序法中所采用的分划方法，以主元为基准，将一个表划分为左右两个子表，左子表中的元素均小于主元，右子表中的元素均大于主元。主元的选择是将表划分为r部分，对找出r个中的 中间值，并求r组的中间值中的中间值。
锦标赛算法：
两两分组比较，大者进入下一轮，知道剩下1个元素max为止。在每次比较中淘汰较小元素，将被淘汰元素记录在淘汰它的元素的链表上。检查max的链表，从中知道最大元素，即second
本科实验报告
课程名称： 算法设计与分析
实验项目： 贪心算法
实验地点： 计算机系实验楼110
专业班级： 物联网1601 学号： 2016002105
学生姓名： 俞梦真
指导教师： 郝晓丽
2018年 05月 04日
实验二 贪心算法
2.1 实验目的与要求
1．理解贪心算法的基本思想；
2．运用贪心算法解决实际问题，加深对贪心算法的理解和运用。
2.2 实验课时
4学时（课内2学时+课外2学时）
2.3 实验原理
贪心算法的思想：
（1）贪心算法（Greedy Approach）能得到问题的最优解，要证明我们所做的第一步选择一定包含着一个最优解，即存在一个最优解的第一步是从我们的贪心选择开始。
（2）在做出第一步贪心选择后，剩下的子问题应该是和原问题类似的规模较小的子问题，为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。
2.4 实验题目
1．上机题目：最小延迟调度问题
给定等待服务的客户集合A={1,2,…,n}，预计对客户i的服务时长为ti>0，T=(t1,t2,…,tn)，客户i希望的服务完成时刻为di>0，D=(d1,d2,…,dn)；一个调度f:A→N，f(i)为客户i的开始时刻。如果对客户i的服务在di之前结束，那么对客户i的服务没有延迟，即如果在di之后结束，那么这个服务就被延迟了，延迟的时间等于该服务的实际完成时刻f(i)+ti减去预期结束时刻di。一个调度f的最大延迟是所有客户延迟时长的最大值maxi∈A{f(i)+ti-di}。附图2所示是不同调度下的最大延迟。使用贪心策略找出一个调度使得最大延迟达到最小。
2．设计思想：
贪心思想，按照他们的截止时间从小到大排序，如果截止时间相同按照花费时间从小到大排序。然后按照f_min（所有客户延迟时长的最大值）=max(works[i].cost+time-works[i].deadline,f_min);寻找最所有客户延迟时长的最大值。
3．代码设计：
//最小延迟调度问题
//输入包含：任务，任务完成需要的时间，完成改任务的截止时间
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
int n;
struct node{
int id;
int cost;
int deadline;
}works[maxn];
bool cmp(node a,node b)
{
if(a.deadline!=b.deadline)
return a.deadline<b.deadline;
else
return a.cost<b.cost;
}
int dp[maxn][maxn];
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d",&works[i].cost);
for(int i=0;i<n;i++)
scanf("%d",&works[i].deadline),works[i].id=i+1;
sort(works,works+n,cmp);
int f_min=0;
int time=0;
for(int i=0;i<n;i++)
{
//if(works[i].cost+time>works[i].deadline)
f_min=max(works[i].cost+time-works[i].deadline,f_min);
//cout<<f_min<<endl;
time+=works[i].cost;
}
printf("Maximum delay:\n");
printf("%d\n",f_min);
printf("Complete the order of tasks:\n");
for(int i=0;i<n;i++)
cout<<works[i].id<<" ";
cout<<endl;
}
return 0;
}
/*样例输入：
5
5 8 4 10 3
10 12 15 11 20*/
运行结果：
2.5 思考题
（1）哈夫曼编码问题的编程如何实现？
答：哈夫曼树，又名最优树，给定n个权值作为n的叶子结点，构造一颗二叉树，若带权路径长度达到最小，成这样的二叉树为最优二叉树，也称哈夫曼树。
实现步骤：1、初始化: 根据给定的n个权值{w1，w2,…..wn..}构成n棵二叉树的集合F={T1,T2….Tn},其中每棵二叉树中只有一个带权Wi的根结点，左右子树均空。2、 找最小树:在F中选择两棵根结点权值最小的树作为左右子树构造一-棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树，上根结点的权值之和。
3、删除与加入: 在F中删除这两棵树，并将新的二叉树加入F中。
4、判断:重复前两步(2和3)，直到F中只含有一棵树为止。该树即为哈夫曼树。
（2）使用贪心策略求解背包问题。
答：首先计算每种物品单位重量的价值vi／wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未达到w，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去直到背包满重为止。算法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O(nlogn)。
（3）分析普里姆算法和克鲁斯卡尔算法中的贪心策略。
答：1、普里姆算法贪心策略：
要记录到S中的下一条边（u，v）是一条不在S中，且使得SU{u,v}的权值之和也是最小的边 时间复杂度：O(n^2) 空间复杂度：O(n^2)
2、克鲁斯卡尔算法中的贪心策略：
选取属于不同联通分量且构成权值最小且不形成回路的两个顶点组成的边、
本科实验报告
课程名称： 算法设计与分析
实验项目： 动态规划
实验地点： 计算机系实验楼110
专业班级： 物联网1601 学号： 2016002105
学生姓名： 俞梦真
指导教师： 郝晓丽
2018年 05月 07日
实验三 动态规划算法
3.1 实验目的与要求
1．理解动态规划算法的基本思想；
2．运用动态规划算法解决实际问题，加深对贪心算法的理解和运用。
3.2 实验课时
4学时（课内2学时+课外2学时）
3.3 实验原理
动态规划（Dynamic Programming）算法思想：把待求解问题分解成若干个子问题，先求解子问题，然后由这些子问题的解得到原问题的解。动态规划求解过的子问题的结果会被保留下来，不像递归那样每个子问题的求解都要从头开始反复求解。动态规划求解问题的关键在于获得各个阶段子问题的递推关系式：
（1）分析原问题的最优解性质，刻画其结构特征；
（2）递归定义最优值；
（3）自底向上（由后向前）的方式计算最优值；
（4）根据计算最优值时得到的信息，构造一个最优解。
3.4 实验题目
1．上机题目：最大子段和问题
给定n个整数（可以为负数）组成的序列(a1,a2,…,an)，使用动态规划思想求该序列的子段和的最大值。注：当所有整数均为负整数时，其最大子段和为0。
例如，对于六元组(-2, 11, -4, 13, -5, -2)，其最大字段和为：a2 + a3 + a4 = 20。
除了动态规划，该问题可以使用顺序求和+比较（蛮力法）和分治法求解，思考其求解过程。
2．设计思想
动态规划思想：dp[i],表示到当前i的最大字段和为多少，而他的字段和时要不就是前面的最大字段和加上本身的数值要不就是自身的数值。状态转移方程：dp[i]=max(dp[i],dp[i-1]+a[i]);
3．代码设计
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=1000+10;
int dp[maxn];
int a[maxn];
//动态规划思想：dp[i],表示到当前i的最大字段和为多少，而他的字段和时要不就是前面的最大字段和加上本身的数值要不就是自身的数值
//dp[i]=max(dp[i],dp[i-1]+a[i]);
int main()
{
int n;
while(cin>>n)
{
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
cin>>a[i],dp[i]=a[i];
int ans=0;
for(int i=1;i<n;i++)
{
dp[i]=max(dp[i],dp[i-1]+a[i]);//
if(dp[i]>ans)
ans=dp[i];
}
cout<<ans<<endl;
}
return 0;
}
3.5 思考题
（1）深刻理解动态规划与递归求解问题的区别是什么？、
答：动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。
（2）动态规划思想解题的步骤是什么？
答：第一步：确定子问题。
在这一步重点是分析那些变量是随着问题规模的变小而变小的， 那些变量与问题的规模无关。
第二步：确定状态：根据上面找到的子问题来给你分割的子问题限定状态
第三步：推到出状态转移方程：这里要注意你的状态转移方程是不是满足所有的条件， 注意不要遗漏。
第四步：确定边界条件：先根据题目的限制条件来确定题目中给出的边界条件是否能直接推导出， 如果不行也可以尝试从边界条件反推（举个例子：a(n)→a(2)有递推关系， 但是a(2)→a(1)不符合上述递推关系， 我们就可以考虑用a(1)来倒推出a(2)， 然后将递推的终点设置为a(2)）;
第五步：确定实现方式：这个依照个人习惯 就像是01背包的两层for循环的顺序
第六步：确定优化方法：很多时候你会发现走到这里步的时候你需要返回第1步重来。首先考虑降维问题（优化内存）， 优先队列、四边形不等式（优化时间）等等。
（3）动态规划思想和贪心算法在求解问题时的区别是什么？
答：共同点: 求解的问题都具有最优子结构性质
区别点:动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。
（4）使用动态规划算法求解最长公共子序列（LCS）问题。
答：LCS问题的最优子结构性质，得其状态转移方程或者说递归式： dp[i][j] 表示记录a[i] b[j]的LSC的长度 时间复杂度： O(m+n);
a[i]==b[j] dp[i-1][j-1]+1;
a[i]!=b[j] max(dp[i-1][j],dp[i][j-1]);
（5）使用动态规划算法求解最长最大字段和问题。
答：动态规划思想：dp[i],表示到当前i的最大字段和为多少，而他的字段和时要不就是前面的最大字段和加上本身的数值要不就是自身的数值。dp[i]=max(dp[i],dp[i-1]+a[i])
本科实验报告
课程名称： 算法设计与分析
实验项目： 回溯算法
实验地点： 计算机系实验楼110
专业班级： 物联网1601 学号： 2016002105
学生姓名： 俞梦真
指导教师： 郝晓丽
2018年 05 月 07 日
实验四 回溯算法
4.1 实验目的与要求
1．通过回溯算法的示例程序理解回溯算法的基本思想；
2．运用回溯算法解决实际问题，进一步加深对回溯算法的理解和运用。
4.2 实验课时
4学时（课内2学时+课外2学时）。
4.3 实验原理
回溯算法（Backtrack）的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
回溯算法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯算法的基本步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
常用剪枝函数：
（1）用约束函数在扩展结点处剪去不满足约束的子树；
（2）用限界函数剪去得不到最优解的子树。
4.4 实验题目
1．上机题目：排兵布阵问题
某游戏中，不同的兵种处于不同的地形上时，其攻击能力也一样，现有n个不同兵种的角色(1, 2, ..., n)，需安排在某战区n个点上，角色i在j点上的攻击力为Aij，使用回溯法设计一个布阵方案，使总的攻击力最大。注：个人决定A矩阵的初始化工作。该问题求解算法的输入数据形如附图4所示。
2．设计思想：
利用回溯法搜索寻找解空间树。深度优先搜索，设立访问标记进行剪枝，并将总共的攻击力作为参数不断传入。寻找最大的攻击力。数值的存储用的是二位数组，用ans_pos记录过程。
3．代码设计
//角色i在j点上的攻击力为Aij
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100+10;
int n,ans=0;
int map[maxn][maxn];
bool vis[maxn];
int pos[maxn],ans_pos[maxn];
void dfs(int cnt,int u)
{
if(cnt==n)
{
if(u>ans)
{
ans=u;
memcpy(ans_pos,pos,sizeof(pos));
}
return;
}
for(int i=0;i<n;i++)
{
if(!vis[i])
{
vis[i]=1;
pos[cnt]=i+1;
dfs(cnt+1,u+map[cnt][i]);
vis[i]=0;
}
}
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&map[i][j]);
memset(vis,0,sizeof(vis));
dfs(0,0);
printf("Max ATC:%d\n",ans);
printf("Postion: ");
for(int i=0;i<n;i++)
printf("%d ",ans_pos[i]);
printf("\n");
}
return 0;
}
/*5
60 40 80 50 60
90 60 80 70 20
30 50 40 50 80
90 40 30 70 90
60 80 90 60 50*/
运行结果：
4.5 思考题
（1）什么是启发式搜索问题？
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
（2）搜索算法的解空间树的如何定义？
答：解决一个问题的所有可能的决策序列就构成了该问题的解空间。通常将解空间画成树的形状，称为解空间树。
（3）0-1背包问题的动态规划算法如何求解？
答：声明一个 大小为 m[n][c] 的二维数组，m[ i ][ j ] 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值 ，那么我们可以很容易分析得出 m[i][j] 的计算方法，
（1） j < w[i] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿m[ i ][ j ] = m[ i-1 ][ j ]
（2） j>=w[i] 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。
状态转移方程：
if(j>=w[i])
m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
else
m[i][j]=m[i-1][j];
（4）n皇后问题使用回溯法如何求解？
答：首先找出解空间：给棋盘的行和列都编上1到N的号码，皇后也给编上1到N的号码。由于一个皇后应在不同的行上，为不失一般性，可以假定第i个皇后将放在第i行上的某列。因此N皇后问题的解空间可以用一个N元组（X1，X2，.....Xn）来表示，其中Xi是放置皇后i所在的列号。这意味着所有的解都是N元组（1，2，3，.......，N）的置换。解空间大小为N！。其次我们看约束条件：因为解空间已经给我们排除了不在同一行（因为每个皇后分别已经对应不同的行号）的约束条件。我们要判断的是不在同一列和不在同一斜线的约束。因为Xi表示皇后所在的列号，所以第k个皇后和第i个皇后同列的判断条件是X（k）=X（i）。所以不同列的判段条件是X（k）！=X（i），1<k<i 。又因为同一斜线的特征是要么行号和列号之和不变（右高左低）要么是行号和列号只差相等（左高右低），所以第k个皇后和第i个皇后在同斜线的判断条件是 i+X（i）= k+X（k) 或 i-X(i) =k-X(k),两式合并得 |X(i)-X(k)|=|i-k| 。
（5）使用回溯法求解装载问题。
答：基本思路： 容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近C1。由此可知，装载问题等价于以下特殊的0-1背包问题。
本科实验报告
课程名称： 算法设计与分析
实验项目： 分支限界算法
实验地点： 计算机系实验楼110
专业班级： 物联网1601 学号： 2016002105
学生姓名： 俞梦真
指导教师： 郝晓丽
2018年 05 月 14 日
实验五 分支限界算法
5.1 实验目的与要求
1．通过分支限界算法的示例程序进一步理解分支限界算法的基本思想；
2．运用分支限界算法解决实际问题，进一步加深对分支限界算法的理解和运用。
5.2 实验课时
4学时（课内2学时+课外2学时）。
5.3 实验原理
分枝限界（Branch-and-Bound）算法是另一种系统地搜索解空间的方法，它与回溯算法的主要区别在于对E-结点的扩充方式。每个活结点有且仅有一次机会变成E-结点。当一个结点变为E-结点时，则生成从该结点移动一步即可到达的所有新结点。在生成的结点中，抛弃那些不可能导出（最优）可行解的结点，其余结点加入活结点表，然后从表中选择一个结点作为下一个E-结点。从活结点表中取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充过程才结束。
有两种常用的方法可用来选择下一个E-结点（虽然也可能存在其他的方法）：
（1）先进先出（F I F O）即从活结点表中取出结点的顺序与加入结点的顺序相同，因此活结点表的性质与队列相同。
（2）（优先队列）最小耗费（LC）或最大收益法在这种模式中，每个结点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活结点表可用最小堆来建立，下一个E-结点就是具有最小耗费的活结点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活结点表，下一个 E-结点是具有最大收益的活结点。
5.4 实验题目
1．上机题目：运动员最佳配对问题
羽毛球队有男女运动员各n人。给定两个n×n矩阵P和Q；P[i][j]表示男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势，Q[i][j]表示女运动员i和男运动员j配对组成混合双打的女运动员竞赛优势（注意：由于多种原因，P[i][j] 未必等于Q[j][i]），男运动员i和女运动员j配对组成混合双打的男女运动员双方总体竞赛优势为P[i][j]* Q[j][i]。用分支限界法设计一个算法，计算男女运动员的最佳配对，即各组男女运动员双方总体竞赛优势的总和达到最大。
2．设计思想
对于n个男运动员，从第1个开始搭配女运动员：第1个有n种搭配方法，第2个有n-1种搭配方法……第n个有n-(n-1)种搭配方法；根据问题给出的示例：输入n的值为3，表示男女运动员各有3名；
男运动员 1 2 3按顺序搭配女运动员，他们分别对应的女运动员可以是：
女运动员 1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1
所以其解空间是{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}，整个问题可看成是1,2,3的全排列问题，将解空间组织成一棵排列树。解空间树的第i层到第i+1层边上的标号给出了变量的值。从树根到叶的任一路径表示解空间中的一个元素。用LC分支界限法的搜索策略搜索整个解空间
3．代码设计
//运动员最佳配对-效益最大
//分支限界法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=100+10;
int n;
int p[maxn][maxn],q[maxn][maxn];
int ans_x[maxn];
int vis[maxn];
struct node{
int dep;
int win;
int *x;
node(int d,int w)
{
x=new int[n+1];
dep=d;
win=w;
}
int get_win()
{
int temp=0;
for(int i=1;i<=dep;i++)
temp+=p[i][x[i]]*q[x[i]][i];
return temp;
}
bool operator <(const node &u)const
{
return win<u.win;
}
};
int bfs()
{
priority_queue<node> q;
node t(0,0);//开始0，效益0；
for(int i=1;i<=n;i++)
t.x[i]=i;//
int ans=0;
while(true)
{
if(t.dep==n)
{
if(t.win>ans)
{
ans=t.win;
copy(t.x,t.x+n+1,ans_x);//复制解向量
break;
}
cout<<ans<<endl;
}
else
{
for(int i=t.dep+1;i<=n;i++)
{
node now(t.dep+1,0);
copy(t.x,t.x+n+1,now.x);
now.x[now.dep]=t.x[i];
now.x[i]=t.x[now.dep];//交换
now.win=now.get_win();
//cout<<"now win: "<<now.win<<endl;
q.push(now);
}
}
if(q.empty())
break;
else
{
t=q.top();
q.pop();
}
}
return ans;
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&p[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&q[i][j]);
printf("Max Competition advantage: %d\n",bfs());
printf("The combination is: ");
for(int i=1;i<=n;i++)
printf("(%d,%d) ",i,ans_x[i]);
printf("\n");
}
return 0;
}
/*样例
3
11 2 2
3 4 5
4 5 6
2 2 2
3 4 5
1 9 4*/
运行结果：
5.5 思考题
（1）批处理作业调度问题的分支限界算法如何求解？
批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，批处理作业调度问题的解空间是一颗排列树。在作业调度问相应的排列空间树中，每一个节点E都对应于一个已安排的作业集。以该节点为根的子树中所含叶节点的完成时间和可表示为： 设|M|=r，且L是以节点E为根的子树中的叶节点，相应的作业调度为{pk,k=1,2,……n}，其中pk是第k个安排的作业。如果从节点E到叶节点L的路上，每一个作业pk在机器1上完成处理后都能立即在机器2上开始处理，即从pr+1开始，机器1没有空闲时间，则对于该叶节点L有：. ?如果不能做到上面这一点，则s1只会增加，从而有：。类似地，如果从节点E开始到节点L的路上，从作业pr+1开始，机器2没有空闲时间，则：.?同理可知，s2是的下界。由此得到在节点E处相应子树中叶节点完成时间和的下界是：? ? ?注意到如果选择Pk，使t1pk在k>=r+1时依非减序排列，S1则取得极小值。同理如果选择Pk使t2pk依非减序排列，则S2取得极小值。?
? ? ?这可以作为优先队列式分支限界法中的限界函数。?
（2）0-1背包问题的分支限界算法如何求解？
对0/1背包问题的解的结构，约束条件，目标函数和状态空间树的分析与使用回溯法时相同。求解0/1背包问题的一个关键问题时设计上下界函数。
目标函数： cost(x)=Σ(0-n-1)px，这是一个求最大值的优化问题。
代价函数：cos(x)=Σ(0-k)px+Σ(k-n-1)px
上下界函数：LBB(x),UBB(x)。
售后服务方案(赠送)
1.售后服务概述
公司长期以来一直致力于提供高质量、完善的支持服务，确保用户的系统稳定运行。
公司拥有一批资深的施工人员，具有丰富的经验，能够很好的解决设备各类故障，强大的用户支持队伍和良好的用户满意度是我们的一大优势。
维护计划及承诺
?一、 项目售后服务内容承诺
我公司贯彻执行：“诚信正直、成就客户、完善自我、追求卓越”的宗旨，对于已经竣工、验收合格的项目进行质量跟踪服务，本着技术精益求精的精神，向用户奉献一流的技术和一流的维护服务。
我公司如果承接了端拾器项目，将严格遵循标书及合同的规定，在保证期内向业主提供该项目的责任和义务。在保修期之后，考虑到设备维护的连续性，建议业主与我公司签订维护合同，以确保此系统项目的正常运行所必需的技术支持和管理支持。
二、 服务与保证期
?在项目验收合格之日起，开始进行售后服务工作，包括以下几个方面：
１、售后服务期； ?２、维护人员； ３、售后服务项目； ４、服务响应时间。
? 三、 售后服务期
? 在项目验收合格之日起，即进入了售后服务期。
售后服务期=质量保证期+质量维护期
? 质量保证期：在质量保证期内，如因质量问题造成的故障，实行免费更换设备、元器件及材料。如因非质量因素造成的故障，收取更换设备、元器件及材料成本费。
质量维护期：在质量保证期之后，即自行进入质量维护期。
我方对所承担端拾器项目提供终身质量维护服务，以不高于本合同设备单价的优惠价格提供所需更换的元器件及材料，另收维护人员工本费。
四、 具体措施承诺
? 1、首先在签订项目合同的同时与客户签订售后服务保证协议书，排除客户的后顾之忧，对客户做出实事求是的、客观的承诺。
2、对已经验收合格交付用户的端拾器项目，在合同期内与用户进行联系，记录用户使用情况，系统运行状况等进行质量跟踪调查，变被动服务为主动服务。
3、对已交工的端拾器项目建立系统运行档案，并进行质量跟踪。
4、系统运行档案记录其端拾器项目运行情况、各类设备使用情况、操作人员操作水平情况及人员流动情况。
5、针对各用户单位操作人员出现的代表性问题，定期对操作人员进行技术培训或到现场培训及指导。
6、正在使用中的系统、设备出现故障时，公司维修服务人员接到报告后及时赴现场处理、维修。
7、对于运行时间较长的端拾器项目，公司维修服务人员定期与客户进行联系询问情况，定期到客户方进行巡视、检查，并做出记录，记录归档保存。
8、施工保证
将选派具有丰富经验的技术人员负责端拾器项目具体施工，保证安装质量及系统使用功能，并保证整个系统运行平稳、高效、可靠。
9、系统保修
作为项目承包单位，我公司将严格遵循招标文件及合同的规定，向业主提供端拾器项目最终验收合格之日起，在保质期范围内免费维修。
10、保修期内设备损坏，经鉴定为设备本身原因造成的故障，我方负责免费维修或者更换；同时负责在保修期内定期对设备提供保养维护服务。
总之，为使业主使用放心、使用方便、保证端拾器项目正常运行，公司全体技术、维护人员本着客户第一的原则，全心全意地为客户着想，全力以赴的进行工作，让我们共同携手，为创造美好的明天而努力工作。
五、保修服务内容及范围
我公司将为所承担的各个端拾器项目提供保修服务，有效期从项目验收后，业主在竣工报告上签字之日起。
1、 响应时间：具体的响应时间将按故障级别划分；
2、 维修地点：用户现场。
我公司负责实施的所有系统项目，在正常环境下做适当使用时所发生的故障，我公司将提供约定保修服务。非当前故障，我公司安排提供服务，但需按收费标准另收费用。
我公司的保修服务仅限于经我公司认定的合格产品。所谓不合格的产品包括：非经我公司供应的产品、非经我公司认定合格的产品及顾客不允许我公司做功能改进的产品。
下列情况所发生的系统损害不包括在保修服务范围内：
1、 使用不适当的工具进行系统维护时造成的系统设备损坏；
2、 现场环境不符合我公司建议的规范；
3、 意外、自然灾害、疏忽及不当使用、战争、暴动、罢工、雷击或电力故障、顾客搬运不当的损坏，经由非我公司人员或其授权的子承包商对系统进行修改和变动；
4.设备的维护和信息处理方式。
六、 系统维护
１、系统运行管理工作
为了保证系统能够长时间的正常运行，我们将进行完善的系统培训，同时制定各个系统项目操作规程，并配合业主制定操作人员责任界面及合理的交接班制度。
２、系统维护保养
我公司的售后服务人员在维护期内将对贵方的系统项目提供服务，使它们保持良好的运行状态。
? ３、月度保养
? 坚持月度维护保养，保证每个系统项目机械装置保持最佳工作状态。
七、维护及服务支持措施
１、电话支持服务
电话服务热线号码以我方提供给业主的号码为准(包括电话和传真号码)。如有更改，我方至少在自更改之日起3天内以电子邮件、传真、电话的方式通知业主。
２、现场排除故障或技术指导
我方在接到业主的电话支持服务请求后，如果不能通过电话支持服务解决设备或产品发生的技术故障，且经双方商议确认需要进行现场支持的情况下，我方将派专业项目技术人员及时前往现场协助业主排除故障。
３、电话咨询服务
对业主在使用设备或产品过程中产生的非故障类问题，我方提供电话咨询服务。
４、投诉受理服务
我方在公司设有用户投诉电话