4．因为1维的邮局问题，所有的点都可以表示在一个实数轴上，假设pi的坐标为xi，i?1,2,?,n。不妨假定?wi?1（不然，可以令w'i?wii?1n?wi?1ni），此
时可以认为wi是xi的权。注意到
?x?xi,ifx?xi d(p,pi)?|x?xi|???xi?x,ifx?xi其中，x代表点p的坐标。于是
m(p)??wid(p,pi)??wi|x?xi|??wi(x?xi)??wi(xi?x) (1)
i?1i?1xi?xxi?xnn如果xk是带权中位数，则
m(pk)??wid(pk,pi)??wi|xk?xi|?i?1i?1nnxi?xk?w(xik?xi)?xi?xk?w(xii?xk) (2)
直接推导可知m(pk)?m(p)，从而证明断言。
问题四．记Size(i,j)?|Mns(i,j)|，对于固定的i(i?2)，分两种情况讨论（画图）：情况1，j??(i)，此时Size(i,j)?Size(i?1,j)；
情况2，j??(i)，此时Size(i,j)?max?Size(i?1,j),Size?i?1,?(i)?1??1?；
?0,j??(i)对于i?1有Size(i,j)??，由此，可以说明电路布线问题具有最优子结
?1,j??(i)构性质，并设计出求该问题的动态规划算法。其时间复杂度为O(n2)。 问题五．设计动态规划算法时，注意淹没规则，因为此时不仅有容量约束还有容积约束。设?v1,W1,V1?和?v2,W2,V2?是两个点偶，当v1?v2而且W1?W2,V1?V2时，称点耦?v1,W1,V1?淹没点耦?v2,W2,V2?。其它部分同0/1背包问题的动态规划算法。设计回溯算法和分枝限界算法时，同时注意到两个约束即可。其余略。 问题六． 用b[j]记序列a[1:j]中最长单调递增子序列的长度，s[j]为序列a[1:j]中所有长度为b[j]的单调递增子序列中最后元素最小的子序列的最后元素。则
?b[j],ifa[j?1]?s[j] b[j?1]???b[j]?1,ifa[j?1]?s[j]根据此递推关系式，可以设计一个求最长单调递增子序列的动态规划算法，该算法时间复杂度为O(n2)。
问题八：假定n个作业的集合为Sn??1,2,?,n?。则双机处理作业问题相当于确定Sn的子集J，使得J中的作业在机器A上处理、其余作业在机器B上处理的
???安排是最省时的安排。此时所用时间为max?a,b??j?j?，即最优安排所用时间j?S\\J??j?J???应为minmax?a,b??j?j?。若记Sn?1??1,2,?,n?1?，则有如下递推关系： J?Snj?S\\J?j?J????????????????minmax?a,b?minminmaxa?a,b,minmaxa,b?b??j?j??n?j?j?J?Sn－1??jn?j???I?SnJ?Sn－1j?S\\Ij?Jj?S\\Jj?S\\J?j?I????j?J??? (4.1)
令m(S,tA,tB)表示机器A需等待时间tA，且机器B需等待时间tB情况下安排作业集合S在两台机器A、B上处理所需的最短时间，则对于任意作业i?S，
m(S,tA,tB)?min?m(S\\{i},ai?tA,tB),m(S\\{i},tA,bi?tB)? (4.2)
n个作业的双机处理问题满足：
m(Sn,0,0)?min?m(Sn?1,an,0),m(Sn?1,0,bn)? (4.3)
(4.2)说明双机调度问题具有最优子结构性质，可以采用动态规划算法。在(4.3)中，如果m(Sn?1,an,0)?m(Sn?1,0,bn)，则作业n安排在机器A上处理，否则安排在机器B上处理。若用xi?1表示第i件作业在机器A上处理，xi?0表示第i件作业在机器B上处理，则不等式m(Sn?1,an,0)?m(Sn?1,0,bn)就决定了xn的取值。根据以上分析不难给出双机调度问题的动态规划算法。
注：此种方法能否推广求解多机调度问题，比如求解3机调度问题？ 问题九：将每件物品用两个和它完全一样的物品来替代，构造一个具有2n件物品的0/1背包问题。为写出数学模型，可以把用于表示物品i装包情况的变量xi用两个变量xi1,xi2表示其被装入背包的可能情况：xi1?xi2?0表示物品i没有被装进背包；xi1?0,xi2?1orxi1?1,xi2?0则表示两件物品i有一件装进背包，而
xi1?1,xi2?1则表示两件物品i都被装进了背包。因而xi?xi1?xi2。
注：这种将整数规划问题转化成0/1规划问题求解方法使得问题的规模增加过大，你能否设计一个较好的方法，使问题规模的增大小些？
第二部分：分析比较
1．试比较复杂性函数的渐进性态与?函数的区别和联系。
2．假定复杂性函数都是定义在正整数集合上的正函数，那么关于渐进上界符号O，如下运算性质那些成立、那些不成立。成立则给出证明、不成立则举出反例。
(1) O(f)?O(g)?O(max(f,g))； (2) O(f)O(g)?O(fg); (3) O(f)/O(g)?O(f/g);
(4) O(cf(n))?O(f(n)),其中c是一个正的常数； (5) O(f)?(f)??(f).
3．何谓递归算法？就2k阶矩阵相乘A?B分别设计递归算法和迭代算法，并比较两个算法的时间和空间复杂度。
4．归并排序和快速排序各自都强调了那方面的进程？
5．试分析求最有生成树的Prim算法和Kruskal算法的时间复杂性，看它们在何种情况下表现各自的优越性。
6．贪心算法和动态规划算法有什么共同点和区别？
7．试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 8．确定性图灵机模型与非确定性图灵机模型的主要区别在那里？确定性图灵机模型下算法的时间复杂度和空间复杂度指的是什么？ 9．什么是多项式时间算法？什么是NP类问题？
10．已经知道如何通过已知的NPC问题去证明另一个NP-问题也是NPC问题的方法，能否给出一个通过已知的P-问题证明另一个判定问题是P-问题？ 11． NP-困难问题与NPC问题是一类问题吗？就旅行商最优问题和旅行商判定问题谈你的看法。
12． 下列问题那些是P-问题、那些是NPC-问题？那些是NP-困难问题？ (1) 最优生成树的判定问题；
例：给定一个赋权（权为正整数）连通图G?(V,E)，一个正整数R。 问：是否存在G的生成树T，其权值不超过R？ (2) 二维匹配问题
例：给定一个二部图G?(V1,V2，E)，|V1|?|V2|，
问：是否存在G的完备匹配，即存在E的子集E1满足：E1中任何两条边
没有公共顶点，而且E1的端点集为V1?V2？
(3) 二元可满足性问题
例：给定逻辑语句C?C1?C2???Cl，其子句定义在布尔变量
X??x1,x2,?,xn?上，而且每个子句的均由两个文字构成Ci?yi?zi，
i?1,2,?,l。
问：是否存在布尔变量的一个真值分配，使得语句取真值？
(4) 三元可满足性问题3SAT(3-Satisfiability)
例：给定布尔变量的一个有限集合U?{u1,u2,?,un}及定义于其上的逻辑语句C?C1?C2???Cm，其中，|Ci|?3，i?1,2,?,m。 问：是否存在U的一个真赋值，使得C为真？ (5) 图的独立集问题
例：对于给定的无向图G?(V,E)和正整数k(?|V|)
问：G是否包含一个k－独立集V'，即是否存在一个子集
V'?V,|V'|?k，使得V'中的任何两个顶点在图中G都不相邻。
~提示：考虑独立集和团的关系：如果V'是图G的团，则V'是G的补图G的
独立集；反之亦然。
(6) 二部图的独立集问题
例：给定一个二部图二部图G?(V1,V2，E)，正整数k?|V1?V2| 问：G是否含有一个不小于k的独立集？ (7) 团问题（CLIQUE）
例：给定一个无向图G(V,E)和一个正整数k。
|V'|?k，且对任意u,v?V'，问：G是否包含一个k团？即是否存在V'?V，有(u,v)?E
(8) 顶点覆盖问题VERTEX-COVER
例：给定无向图G(V,E)和一个正整数k
问：G是否有k覆盖，即是否存在V'?V,|V'|?k，使得对任意(u,v)?E，
有u?V'orv?V'。
(9) 定和子集问题DSS
例：给定非负整数集合S，正整数M 问：是否存在子集C?S,使得?c?M
c?C(10)精确覆盖问题XC
例：已知有限集合S的子集族C
问：C是否包含一个精确覆盖，即是否存在C'?C，使得C'中元素互不相
交，且?c?S
c?C'(11) 划分问题PARTS
例：已知一个有限集合A，及对每个a?A赋予的权值s(a)?Z 问：是否存在一个子集A'?A，使得?s(a)?s?A'??s(a)
s?A\\A'(12) 0/1背包判定问题 KPS
例：给定一个有限集合U，对于每个a?U，对应一个值w(a)?Z和另一
个值v(a)?Z。另外给定一个约束值B?Z和目标K?Z
问：是否存在U的一个子集U'?U，使得?w(a)?B，而且?v(a)?K
a?U'a?U'????(13) 0/1背包最优问题 (14) 旅行商判定问题
