算法答案

目录第二讲分治法................................................................2循环赛日程表问题.........................................................2第三讲动态规划..............................................................6矩阵连乘问题.............................................................6最长公共子序列...........................................................70-1背包问题.............................................................9最大K乘积问题..........................................................11第四讲贪心法...............................................................13背包问题................................................................13活动安排问题............................................................14最优装载................................................................15第五讲回溯法...............................................................18装载问题................................................................18八皇后问题..............................................................20图的m着色问题..........................................................24第六讲分支限界法...........................................................27布线问题_队列式.........................................................270-1背包问题_队列式.....................................................300-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个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。12345671234567821436785341278561234321856712345678143212143658721431234127856321421432187654321（1）（2）（3）图12个、4个和8个选手的比赛日程表图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。//代码如下：voidmatchtable(inta[][N],intk){intn=1,m=1;for(inti=1;i=k;i++)n*=2;for(inti=0;in;i++)a[i][0]=i+1;for(ints=0;sk;s++)//k个阶段，从左到右{n/=2;for(intt=0;tn;t++)//每个阶段有t次循环{for(intj=m;j2*m;j++)for(inti=m;i2*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个选手，第二列到第六列表示各个选手在第一天到第五天的所遇到的选手。123456215364361245456132542613634521在这里算法设计的难点就是分治后的合并问题。这里我就结合上面给出的6个选手的示例来进行表述。首先，将6个选手分为对等的两组，每组3个选手。然后再递归的将3个选手分为对等两组，每组2个选手。在2个选手情况下，这两个选手比赛。可以得到两个选手的日程安排表是：1221接下来的任务是合并这两组2个选手的日程表得到3个选手的日程安排表，这里我先假设有4个选手参加比赛则：12213443接下来的比赛里，第二天让1和3比赛，2和4比赛；第三天让1和4比赛，2和3比赛，即让前一组的选手，循环的和后一组的选手比赛，可得到比赛日程安排表是：1234214334124321这里要得到的是3个选手的日程安排表，则第4个选手是假想的选手将其用0来表示则得到3个选手的日程安排表：123021033012接下来的任务是合并这两个3个选手的日程安排表得到6个选手的日程安排表，这里我们的两组选手前3天的比赛情况如下：123021033012456054066045其中第一天选手3和选手6都没有对手，让他们两个比赛；第二天选手2和选手5没有对手，让他们两个比赛，；第三天选手1和选手4没有对手，让他们两个比赛。这就可以得到合并后6个选手前三天的比赛日程安排表：123421533612456154266345将在前三天比过赛的两组的选手对应的列出来：123456在这里可以看到合并的两组中3和6，2和5，1和4都已经比过了，这里就跳过这些选手的比赛，然后两个组循环比赛即：123564和123645这样就得到了6个选手的比赛完整的日程安排表：123456215364361245456132542613634521三、证明算法的正确性：（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；当ij时，可利用最优子结构性质来计算m[i,j]。事实上，若计算Ai…j的最优次序在Ak和Ak+1之间断开，i≤kj，则：m[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]中，则相应的最优解便可递归地构造出来。#includestdio.hintr[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;kj;k++){temp=m(i,k)+m(k+1,j)+r[i-1]*r[k]*r[j];if(tempmin){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的最长公共子序列。证明见教材