搜索与回溯四大问题

搜索与回溯四大问题,制作者：depthfirst,问题一邮票问题(youpiao.pas/c/cpp),问题描述设有已知面额的邮票m种，每种有n张。用总数不超过n张的邮票进行组合，能组合的邮票面额中可以连续出现面额数最多是多少？(1=m=100,1=n=100,1=邮票面额=255)输入:第一行：n和m的值，中间用一空格隔开。第二行：a1.m(面额)，每个数中间用一空格隔开。输出:连续面额数的最大值样例输入(youpiao.in)43124样例输出(youpiao.out)14,问题分析这是一道对已知数进行组合的问题。常规方法是从最低面额开始，将所有的数的组合探求一遍，同时将所得到的值记录下来，然后对连续出现地数值进行统计，最后找出最值。从算法复杂度的角度来讲并不麻烦，但m和n值的大小始终是制约搜索速度的主要因素。因此如果在搜索过程中不加一定的优化，程序必然超时，因此我们必须要充分挖掘出其内含的限制条件，必要时还要用数学方法帮助解决。,优化一：如果是通过小面额的组合来求得总的面额值，不仅解题难度较大，而且对较大的M和N而言，程序必然超时。但如果倒过来，将给定的面值进行拆分，解题的难度就大大减少。试以面额值为8为例（等式说明：4*2表示面值为4的邮票有2张）：84*24*1+2*1+1*24*1+2*22*4优化二：在构成邮票面额时，难免出现同一个面额不同的组合的情况，根据题目要求只要某种面额出现一种组合就可以了，所以我们可以采用一些数学技巧来减少多余的组合。这样就可以加快程序运行速度。结合刚才对8进行拆分的例子，我们可以注意到最容易实现的的用邮票数最少的方案。给我们的启示是：对邮票组合面值的探求可以从大面值的邮票开始。优化三：根据题意，有一个很明显的限制条件就是所用邮票总数不超过n张，这个条件可以带来两个方面的信息：一是指出了邮票面额的最大值为n*am或是题目给出的255；另一就是限定了总张数的最值为n，结合优化一的方法，可以最大限度地“剪枝”。,参考过程：a：array1.100ofinteger；记录m种不同的面值，并由低到高排列b:array1.255ofinteger；记录可能出现的面额n,m:integer；maxlong:integer；记录面额连续出现的最多数proceduresearch(k,n,x:integer)；k表示第k个已知面额，n表示可用已知面额的最多数量，x表示目前已构成的面额值vari:integer；beginif(n=0)or(k=0)thenexit；fori:=ndownto0dobeginx:=x+ak*i；n:=n-i；bx:=bx+1；search(k-1,n,x)；n:=n+i；x:=x-ak*i；end；end；,问题二N皇后问题(nqueen.pas/c/cpp),问题描述在N*N的棋盘上放置N（1=nnthenbeginprint;exit;end;forj:=1tondoifbjandci+janddi-jthenbeginai:=j;bj:=false;ci+j:=false;di-j:=false;ifinthentry(i+1)elseprint;bj:=true;ci+j:=true;di-j:=true;end;end;,问题三自然数的拆分(chaifen.pas/c/cpp),问题描述输入自然数n（1=n=30），然后将其拆分成由若干数相加的形式，参与加法运算的数可以重复。输入：待拆分的自然数n输出：若干数的加法式子样例输入(chaifen.in)7样例输出(chaifen.out)1+61+1+51+1+1+41+1+1+1+31+1+1+1+1+21+1+1+1+1+1+11+1+1+2+21+1+2+31+2+41+2+2+21+3+32+52+2+33+4,问题分析简单的搜索回溯，只是不断拆分最后一个数再回溯。等式中后一个数必须大于等于前一个数，因为这个可以避免重复和提高效率。我们用一个数组ai来记录拆分的数字，用bi记录剩下的数字。k记录第几个拆分的数字。每次拆分都可以把ai都打印出来。把剩下的数字bi在进行拆分，并且是从i开始拆分的,参考过程,proceduresearch(start,m,k:integer);vari,j:integer;beginfori:=startto(mdiv2)dobeginak:=i;bk:=m-i;forj:=1tokdowrite(aj,+);writeln(bk);search(i,bk,k+1);end;end;,问题四校园迷宫问题描述李华被教育局分配到了红星学校，当然是陪着很多人的。不知转了多少次车，总算到了。可惜的是，学校像个迷宫一样，只在门口贴了张学校地图。李华就开始研究地图了，但是学校错综复杂，等找到目的地，早就开考了。为此，李华取出随身携带的微型电脑。注：只能往4个方向走：上、下、左、右。输入格式第1行，二个数，N，M。接下来是一个N*M的矩阵，表示这个学校。（有N行，M列）。矩阵由2个数字组成。0：路；1：墙。路能走，墙不能走（这是基本常识,不过还是提醒一下，不然哪个牛又要飞檐走壁了）。再是2行，第1行2个数X1，Y1表示校门口的坐标（即校门口在矩阵的第X1行，第Y1列）。第2行2个数X2，Y2表示鄙人的考场的坐标（即校门口在矩阵的第X2行，第Y2列）。数据范围：0M，N=2000。0X1，X2=N，0Y1，Y2=M。输出格式一个数，表示最少要走的步数。如果走不到，则输出NoAnswer!样例输入5511111111001000100100111014154样例输出6,注意：本ppt内容确实