算法 经典程序文档.docx
《算法 经典程序文档.docx》由会员分享，可在线阅读，更多相关《算法 经典程序文档.docx（47页珍藏版）》请在冰点文库上搜索。
算法经典程序文档
目录
第二讲分治法2
循环赛日程表问题2
第三讲动态规划6
矩阵连乘问题6
最长公共子序列7
0-1背包问题9
最大K乘积问题11
第四讲贪心法13
背包问题13
活动安排问题14
最优装载15
第五讲回溯法18
装载问题18
八皇后问题20
图的m着色问题24
第六讲分支限界法27
布线问题_队列式27
0-1背包问题_队列式30
0-1背包问题_优先队列式32
第二讲分治法
循环赛日程表问题
问题描述：
设有n=2k个运动员要进行网球循环赛。
现要设计一个满足以下要求的比赛日程表：
（1）每个选手必须与其他n-1个选手各赛一次；
（2）每个选手一天只能参赛一次；
（3）循环赛在n-1天内结束。
请按此要求将比赛日程表设计成有n行和n-1列的一个表。
在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。
其中1≤i≤n，1≤j≤n-1。
按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。
递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。
这时只要让这两个选手进行比赛就可以了。
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 1 4 3 6 7 8 5
3 4 1 2 7 8 5 6
1 2 3 4 3 2 1 8 5 6 7
1 2 3 4 5 6 7 8 1 4 3 2
1 2 1 4 3 6 5 8 7 2 1 4 3
1 2 3 4 1 2 7 8 5 6 3 2 1 4
2 1 4 3 2 1 8 7 6 5 4 3 2 1
（1）
（2） （3）
图1 2个、4个和8个选手的比赛日程表
图1所列出的正方形表（3）是8个选手的比赛日程表。
其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。
据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。
依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。
// 代码如下：
void matchtable（int a[][N], int k）
...{
int n=1, m=1;
for （int i=1; i<=k; i++）
n *= 2;
for（int i=0; i a[i][0]=i+1;
for（int s=0; s...{
n /= 2;
for（int t=0; t ...{
for（int j=m; j<2*m; j++）
for（int i=m; i<2*m; i++）
...{
// 类似于fft中的蝴蝶算法操作，十字形交叉赋值
a[i-m+2*t*m][j] = a[i+2*t*m][j-m];
a[i+2*t*m][j] = a[i-m+2*t*m][j-m];
}
}
m *= 2;
}
}
附：
P602-35
一、问题描述：
设有n个运动员要进行网球循环赛。
设计一个满足以下要求的比赛日程表：
（1）每个选手必须与其他n-1个选手各赛一次；
（2）每个选手一天只能赛一次；
（3）当n是偶数时，循环赛进行n-1天。
当n是奇数时，循环赛进行n天。
二、问题分析和算法设计：
按分治策略，可以将所有的选手对分为两组（如果n是偶数，则直接分为n/2每组，如果n是奇数，则取（n+1）/2每组），n个选手的比赛日程表就可以通过为（n/2或（n+1）/2）个选手设计的比赛日程表来决定。
递归地用这种一分为二的策略对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。
这时只要让这两个选手进行比赛就可以了。
下图给出的是六个选手的比赛日程表，其中第一列表示1-6个选手，第二列到第六列表示各个选手在第一天到第五天的所遇到的选手。
123456
215364
361245
456132
542613
634521
在这里算法设计的难点就是分治后的合并问题。
这里我就结合上面给出的6个选手的示例来进行表述。
首先，将6个选手分为对等的两组，每组3个选手。
然后再递归的将3个选手分为对等两组，每组2个选手。
在2个选手情况下，这两个选手比赛。
可以得到两个选手的日程安排表是：
12
21
接下来的任务是合并这两组2个选手的日程表得到3个选手的日程安排表，这里我先假设有4个选手参加比赛则：
12
21
34
43
接下来的比赛里，第二天让1和3比赛，2和4比赛；第三天让1和4比赛，2和3比赛，即让前一组的选手，循环的和后一组的选手比赛，可得到比赛日程安排表是：
1234
2143
3412
4321
这里要得到的是3个选手的日程安排表，则第4个选手是假想的选手将其用0来表示则得到3个选手的日程安排表：
1230
2103
3012
接下来的任务是合并这两个3个选手的日程安排表得到6个选手的日程安排表，这里我们的两组选手前3天的比赛情况如下：
1230
2103
3012
4560
5406
6045
其中第一天选手3和选手6都没有对手，让他们两个比赛；第二天选手2和选手5没有对手，让他们两个比赛，；第三天选手1和选手4没有对手，让他们两个比赛。
这就可以得到合并后6个选手前三天的比赛日程安排表：
1234
2153
3612
4561
5426
6345
将在前三天比过赛的两组的选手对应的列出来：
123
456
在这里可以看到合并的两组中3和6，2和5，1和4都已经比过了，这里就跳过这些选手的比赛，然后两个组循环比赛即：
123
564
和
123
645
这样就得到了6个选手的比赛完整的日程安排表：
123456
215364
361245
456132
542613
634521
三、证明算法的正确性：
（1）在n=2时，就这两个选手比赛，比赛只进行一天，这也是算法的初始情况，算法成立。
（2）在n=k时，
如果k为偶数，则将k个选手分为k/2的两组，这样按问题的要求k个选手共比赛k-1天，k/2个选手如果是偶数则比赛（k/2）-1天，在合并的时候两组k/2个选手循环比赛需要k/2天，则先分组后合并共需要（k/2）-1+（k/2）=k-1天；k/2个选手如果是奇数则比赛k/2天，在合并的时候两组中每个选手都相对应的比赛过了一次，所以两组k/2个选手循环比赛需要（k/2）-1天，则先分组后合并共需要（k/2）+（k/2）-1=k-1天。
如果k为奇数的情况和k为偶数的情况类似。
四、算法的实现：
第三讲动态规划
矩阵连乘问题
对于矩阵连乘积的最优计算次序问题，设计算Ai…j,1≤i≤j≤n，所需的最少数乘次数为m[i,j]，原问题的最优值为m[1,n]。
●当i=j时，Ai…j=Ai为单一矩阵，无需计算，因此m[i,i]=0，i=1,2,…,n；
●当i事实上，若计算Ai…j的最优次序在Ak和Ak+1之间断开，i≤km[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj
由于在计算时我们并不知道断开点A的位置，所以A还未定。
不过k的位置只有j-i个可能，即k∈{i,i+1,…,j-1}。
因此k是这j-i个位置中计算量达到最小的那一个位置。
从而m[i,j]可以递归地定义为：
m[i,j]给出了最优值，即计算Ai…j所需的最少数乘次数。
同时还确定了计算Ai…j的最优次序中的断开位置k，也就是说，对于这个k有m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj。
若将对应于m[i,j]的断开位置k记录在s[i,j]中，则相应的最优解便可递归地构造出来。
#include
intr[7]={30,35,15,5,10,20,25};
ints[7][7];
longintm（inti,intj）
{
intk;
longintmin,temp;
if（i==j）
{
return0;
}
min=m（i,i）+m（i+1,j）+r[i-1]*r[i]*r[j];
s[i][j]=i;
for（k=i+1;k{
temp=m（i,k）+m（k+1,j）+r[i-1]*r[k]*r[j];
if（temp{
min=temp;
s[i][j]=k;
}
}
/*printf（"[%d,%d]=%ld,%d\n",i,j,min,s[i][j]）;*/
returnmin;
}
voiddisp（inti,intj）
{
if（i==j）
return;
disp（i,s[i][j]）;
disp（s[i][j]+1,j）;
printf（"A[%d,%d]||A[%d,%d]\n",i,s[i][j],s[i][j]+1,j）;
}
main（）
{
clrscr（）;
printf（"%ld\n",m（1,6））;
disp（1,6）;
}
最长公共子序列
若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：
zj=xij。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则：
（1）若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。
（2）若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。
（3）若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。
证明见教材P72面。
由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。
因此，最长公共子序列问题具有最优子结构性质。
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。
用c[i][j]记录序列和的最长公共子序列的长度。
其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。
当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。
故此时C[i][j]=0。
其他情况下，由最优子结构性质可建立递归关系如下：
#include"stdio.h"
charx[8]={'','A','B','C','B','D','A','B'};
chary[7]={'','B','D','C','A','B','A'};
intc[8][7],b[8][7];
intlcsLength（）
{
inti,j;
for（i=1;i<=7;i++）
c[i][0]=0;
for（j=1;j<=6;j++）
c[0][j]=0;
for（i=1;i<=7;i++）
{
for（j=1;j<=6;j++）
{
if（x[i]==y[j]）
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
else
{
if（c[i-1][j]>=c[i][j-1]）
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
}
returnc[7][6];
}
voidlcs（inti,intj）
{
if（i==0||j==0）
return;
if（b[i][j]==1）
{
lcs（i-1,j-1）;
printf（"%c",x[i]）;
}
else
{
if（b[i][j]==2）
lcs（i-1,j）;
else
lcs（i,j-1）;
}
}
voidmain（）
{
clrscr（）;
printf（"LCSLength=%d",lcsLength（））;
printf（"\nLCS:
\n"）;
lcs（7,6）;
}
0-1背包问题
在该问题中需要决定x1..xn的值。
假设按i=1，2，...，n的次序来确定xi的值。
如果置x1=0，则问题转变为相对于其余物品（即物品2，3，.，n），背包容量仍为c的背包问题。
若置x1=1，问题就变为关于最大背包容量为c-w1的问题。
现设r?
{c，c-w1}为剩余的背包容量。
在第一次决策之后，剩下的问题便是考虑背包容量为r时的决策。
不管x1是0或是1，[x2，.，xn]必须是第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案[y2，.，yn]，因而[x1，y2，.，yn]是一个更好的方案。
假设n=3,w=[100,14,10],p=[20,18,15],c=116。
若设x1=1，则在本次决策之后，可用的背包容量为r=116-100=16。
[x2，x3]=[0,1]符合容量限制的条件，所得值为15，但因为[x2，x3]=[1，0]同样符合容量条件且所得值为18，因此[x2，x3]=[0，1]并非最优策略。
即x=[1，0，1]可改进为x=[1，1，0]。
若设x1=0，则对于剩下的两种物品而言，容量限制条件为116。
总之，如果子问题的结果[x2，x3]不是剩余情况下的一个最优解，则[x1，x2，x3]也不会是总体的最优解。
在此问题中，最优决策序列由最优决策子序列组成。
假设m（i,y）表示剩余容量为y，剩余物品为i，i+1，...，n时的最优解的值，即：
利用最优序列由最优子序列构成的结论，可得到m的递归式为：
当y>=wi时：
m（i,y）=max{m（i+1,y）,m（i+1,y-wi）+vi}①式
当0<=ym（i,y）=m（i+1,y）②式
m（1,c）是初始时背包问题的最优解。
以本题为例：
若0≤y＜10，则m（3,y）=0；若y≥10，m（3,y）=15。
利用②式，可得m（2,y）=0（0≤y＜10）；m（2，y）=15（10≤y＜14）；m（2，y）=18（14≤y＜24）和m（2，y）=33（y≥24）。
因此最优解m（1,116）=max{m（2，116），m（2，116-w1）+p1}=max{m（2，116），m（2，16）+20}=max{33，38}=38。
现在计算xi值，步骤如下：
若m（1,c）=m（2,c），则x1=0，否则x1=1。
接下来需从剩余容量c-w1中寻求最优解，用m（2,c-w1）表示最优解。
依此类推，可得到所有的xi（i=1.n）值。
在该例中，可得出m（2,116）=33≠m（1,116），所以x1=1。
接着利用返回值38-p1=18计算x2及x3，此时r=116-w1=16，又由m（2,16）=18，得m（3,16）=14≠m（2,16），因此x2=1，此时r=16-w2=2，所以m（3,2）=0，即得x3=0。
#include
intn=5,c=10;
intw[6]={0,2,2,6,5,4};
intv[6]={0,6,3,5,4,6};
intm（inti,intj）
{
intmax,temp;
if（i==n）
{
if（j>=w[n]）
returnv[n];
else
return0;
}
max=m（i+1,j）;
if（j>=w[i]）
{
temp=m（i+1,j-w[i]）+v[i];
if（temp>max）
max=temp;
}
returnmax;
}
voidtrace（）
{
inti,temp=c;
intx[6];
for（i=1;i{
if（m（i,temp）==m（i+1,temp））
{
x[i]=0;
}
else
{
x[i]=1;
temp=temp-w[i];
}
}
if（m（n,temp）>0）
x[n]=1;
else
x[n]=0;
for（i=1;i<=n;i++）
printf（"x%d=%d",i,x[i]）;
}
main（）
{
inti;
clrscr（）;
printf（"max=%d\n",m（1,10））;
trace（）;
}
最大K乘积问题
设conv（s,t）是I的从s位开始的t位的数字组成的十进制数。
f（i,j）表示I（0,i）的最大j乘积，则f（i,j）具有最优子结构性质。
计算f（i,j）的动态规划递归式如下。
f（i,j）=max{f（k,j-1）*conv（k,i-k）}
voidslove（intn,intm）
{
inti,j,k;
inttemp,maxt,tk=0;
for（i=1;i<=n;i++）
{
f[i][1]=conv（0,i）;
}
for（j=2;j<=m;j++）
{
for（i=j;i<=n;i++）
{
for（k=1,temp=0;k{
maxt=f[k][j-1]*conv（k,i-k）;
if（temp{
temp=maxt;
tk=k;
}
}
f[i][j]=temp;
ka[i][j]=tk;
}
}
}
第四讲贪心法
背包问题
把物体i的Xi部分（1≤i≤n，0≤Xi≤1）装入背包中，使背包内所放物体的价值最高ΣPiXi且ΣWiXi≤m。
#include
floatw[3]={18,15,10};
floatp[3]={25,24,15};
intn=3;
floatm=20;
floats=0,x[4]={0,0,0,0};
voidsort（）
{
inti,j;
floattemp;
for（i=0;i{
for（j=i+1;j{
if（p[i]/w[i]{
temp=p[i];
p[i]=p[j];
p[j]=temp;
temp=w[i];
w[i]=w[j];
w[j]=temp;
}
}
}
}
floatkn（）
{
inti;
for（i=0;i{
if（w[i]>m）
{
x[i]=m/w[i];
s=s+x[i]*p[i];
break;
}
x[i]=1;
m=m-w[i];
s=s+p[i];
}
returns;
}
main（）
{
inti;
clrscr（）;
sort（）;
printf（"Themax=%f\n",kn（））;
for（i=0;iprintf（"%f",x[i]）;
}
活动安排问题
由于输入的活动以其完成时间的非减序排列，所以每次总是选择具有最早完成时间的相容活动加入集合A中。
直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。
也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
最优子结构性质：
若A是关于E的活动安排问题的包含活动1的一个最优解，刚相容活动集合A′=a-{1}是关于E′={i∈E:
si≥f1}的活动安排问题的一个最优解。
此算法一开始选择活动1，然后依次检查活动i是否与当前已选择的所有活动相容。
若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。
贪心算法并不总能求得问题的整体最优解。
但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。
这个结论可以用数学归纳法证明。
证明参看教材P109
#include"stdio.h"
ints[12]={0,1,3,0,5,3,5,6,8,8,2,12};
intf[12]={0,4,5,
升级会员 