2022年ACM经典算法[定 .pdf

《2022年ACM经典算法[定 .pdf》由会员分享，可在线阅读，更多相关《2022年ACM经典算法[定 .pdf（45页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、ACM 竞赛经典算法计算机与信息技术学院名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 45 页 - - - - - - - - - 目录第四次课深度搜索 . 3第五次课深搜2 . 11 第六次课深搜（）. 14 第七次课深搜（） . 21 第八次课宽搜（ 1）. 29 第九次课宽搜（2）+双向搜索 . 35 第十次课启发式搜索A* （宽搜的变式）. 42 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

2、师精心整理 - - - - - - - 第 2 页，共 45 页 - - - - - - - - - 第四次课深度搜索在我们遇到的一些问题当中，有些问题我们不能够确切的找出数学模型，即找不出一种直接求解的方法，解决这一类问题，我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探，按照一定的顺序、规则，不断去试探，直到找到问题的解，试完了也没有找到解，那就是无解，试探时一定要试探完所有的情况（实际上就是穷举）；对于问题的第一个状态，叫初始状态，要求的状态叫目标状态。搜索就是把规则应用于实始状态，在其产生的状态中，直到得到一个目标状态为止。产生新的状态的过程叫扩展（由一个状态，应用规则，产生

3、新状态的过程）搜索的要点： （1）初始状态；（2）重复产生新状态；（3）检查新状态是否为目标，是结束，否转（2） ；如果搜索是以接近起始状态的程序依次扩展状态的，叫宽度优先搜索。如果扩展是首先扩展新产生的状态，则叫深度优先搜索。深度优先搜索深度优先搜索用一个数组存放产生的所有状态。（1）把初始状态放入数组中，设为当前状态；（2）扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态；（3）判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态；（4）判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。（5）如果数组为空，说明无解。（6）转到（

4、）对于pascal 语言来讲，它支持递归，在递归时可以自动实现回溯（利用局部变量）所以使用递归编写深度优先搜索程序相对简单，当然也有非递归实现的算法。1、迷宫（左上角入口，右下角出口，找到一条通路。）程序如下：const 11 10 101 1 1 1 1 0 0 0 1 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 45 页 - - - - - - - - - d:array1.4,1.4of integer=(1,1,0,0),(0,1,1,1),(1,1,0,

5、1),(0,1,1,1); c:array1.4,1.2of -1.1=(0,1),(0,-1),(1,0),(-1,0); var a:array1.16,1.2of integer; i,j:integer; procedure play(k:integer); var i:integer; begin if (ak,1=4)and(ak,2=4) then begin for i:=1 to k do write(,ai,1,ai,2,); writeln; readln; exit; end; for i:=1 to 4 do if (ak,1+ci,10)and(ak,1+ci,10

6、)and(ak,2+ci,25) then if dak,1,ak,2=1 then begin dak,1,ak,2:=2; ak+1,1:=ak,1+ci,1; ak+1,2:=ak,2+ci,2; play(k+1); dak,1,ak,2:=1; end; end; begin fillchar(a,sizeof(a),0); a1,1:=1;a1,2:=1; play(1); end. 2、8 数码八数码问题是指这样一种游戏：将分别标有数字1，2，3， 8 的八块正方形数码牌任意地放在一块33 的数码盘上。 放牌时要求不能重叠。于是， 在 3 3 的数码盘上出现了一个空格（ 0 表示

7、空格）。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。如下图所示：5 6 7 4 0 8 3 2 1 5 0 7 4 6 1 3 8 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 45 页 - - - - - - - - - 程序如下：type node=array1.3,1.3of 0.8; const st:node=(2,8,3),(1,6,4),(7,0,5); gl:node=(1,2,3),(8,0,

8、4),(7,6,5); rl:array1.4,1.2of-1.1=(0,1),(0,-1),(1,0),(-1,0); var a:array1.20of node; function result(k:integer):boolean; var i,x,y:integer; begin result:=false; for x:=1 to 3 do for y:=1 to 3 do if ak,x,yglx,y then exit; result:=true; end; procedure look(k:integer;var x,y:integer); var i,j:integer;

9、begin for i:=1 to 3 do for j:=1 to 3 do if ak,i,j=0 then begin x:=i;y:=j;end; end; procedure print(k:integer); var i,x,y:integer; begin for i:=1 to k do begin writeln(step:,i); for x:=1 to 3 do begin for y:=1 to 3 do write(ai,x,y:3); writeln; end; writeln(-); end; 名师资料总结 - - -精品资料欢迎下载 - - - - - - -

10、- - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 45 页 - - - - - - - - - end; function nrep(k:integer):boolean; var i,x,y:integer; f:boolean; begin nrep:=false; for i:=1 to k-1 do begin f:=true; for x:=1 to 3 do for y:=1 to 3 do if ai,x,yak,x,y then begin f:=false;break;break;end; if f then exit; e

11、nd; nrep:=true; end; procedure step(k:integer); var i,x,y:integer; begin if k=20 then exit; if result(k) then begin print(k);exit;end; look(k,x,y); for i:=1 to 4 do begin if (x+rli,1=1)and(x+rli,1=3)and(y+rli,2=1)then begin ak+1:=ak; ak+1,x+rli,1,y+rli,2:=ak,x,y; ak+1,x,y:=ak,x+rli,1,y+rli,2; if nre

12、p(k+1) then step(k+1); end; end; end; begin a1:=st; step(1); end. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 45 页 - - - - - - - - - 3、跳马（ 5*5）国际象棋8*8 棋盘上某个位置的一只马，按马的行走规则，每个方格进入一次.，它是否可能只走63 步，正好走过除起点外的其他63 个位置各一次？如果有一种这样的走法，则称所走的这条路线为一条马的周游路线。试设计一个算法找出这样一条马

13、的周游路线并输出。本题采用5*5 的棋盘。程序如下：const d:array1.8,1.2of -2.2=(-2,1),(-2,-1),(1,2),(1,-2),(2,-1),(2,1),(-1,-2),(-1,2); var a:array1.5,1.5of 0.1; procedure print; var i,j:integer; begin for i:=1 to 5 do begin for j:=1 to 5 do write(ai,j:3); writeln; end; readln; end; procedure play(x,y:integer); var i:intege

14、r; begin if (x=5)and(y=5) then begin print;exit;end; for i:=1 to 8 do if (x+di,10)and(x+di,10)and(y+di,2目标 (40,40.0) 程序如下：const v:array1.3of integer=(80,50,30); var a:array1.30,1.3of integer; procedure print(k:integer); var i:integer; begin for i:=1 to k do writeln(step:,i,ai,1:3,ai,2:3,ai,3:3); rea

15、dln; end; function nrep(k:integer):boolean; var i:integer; begin nrep:=false; for i:=1 to k-1 do if (ai,1=ak,1)and(ai,2=ak,2)then exit; nrep:=true; end; procedure step(k:integer); var i,j:integer; begin if (ak,1=40)and(ak,2=40) then begin print(k);exit;end; for i:=1 to 3 do for j:=1 to 3 do if (ij)a

16、nd(ak,i0)and(ak,jvj )then begin ak+1,i:=ak,i+ak,j-vj; ak+1,j:=vj;end else begin ak+1,i:=0;ak+1,j:=ak,i+ak,j;end; if nrep(k+1) then step(k+1); end; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 45 页 - - - - - - - - - end; begin a1,1:=80; a1,2:=0; a1,3:=0; step(

17、1); end. 5、狼、羊、菜过河（农夫过河问题）规则是：猎人每次只能带一样过河，而狼吃羊，羊吃菜，不能没有猎人在时在一起。算出过河的方案。程序如下：var a:array1.30,1.4of integer; procedure print(k:integer); var i:integer; begin for i:=1 to k do writeln(step:,i,ai,1:3,ai,2:3,ai,3:3,ai,4:3); readln; end; function can(k:integer):boolean; var i:integer; begin can:=false; if

18、 (ak,2=ak,3)and(ak,2ak,1)or(ak,3=ak,4)and(ak,3ak,1) then exit; i:=k-2; while i0 do begin if (ai,1=ak,1)and(ai,2=ak,2)and(ai,3=ak,3)and(ai,4=ak,4) then exit; i:=i-2; end; can:=true; end; procedure step(k:integer); var i:integer; begin if ak,1+ak,2+ak,3+ak,4=0 then begin print(k);exit;end; for i:=1 to

19、 4 do 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 45 页 - - - - - - - - - begin if i1 then begin ak+1:=ak; ak+1,i:=1-ak,i; ak+1,1:=1-ak,1; end else begin ak+1:=ak; ak+1,1:=1-ak,1; end; if can(k+1) then step(k+1); end; end; begin a1,1:=1; a1,2:=1; a1,3:=1; a1,

20、4:=1; step(1); end. 6、野人和传教士过河?野人和传教士各三人，小船只能载两人，要求野人的人数不能多于传教士。算出过河的方案总数。程序如下： const c:array1.5,1.2of 0.2=(1,0),(0,1),(2,0),(0,2),(1,1); var a:array1.30,1.2of integer; procedure print(k:integer); var i,j:integer; begin for i:=1 to k do begin writeln(step:,i,ai,1:3,ai,2:3); end; end; function can(k:

21、integer):boolean; var i:integer; begin can:=false; if (ak,13)or(ak,13)or(ak,2ak,2)and(ak,20)or(ak,1ak,2)and(ak,20 do begin if (ai,1=ak,1) and(ai,2=ak,2) then exit; i:=i-2; end; can:=true; end; procedure step(k,p:integer); var i:integer; begin if ak,1+ak,2=0 then begin print(k);exit;end; for i:=1 to

22、5 do begin ak+1,1:=ak,1+p*ci,1; ak+1,2:=ak,2+p*ci,2; if can(k+1) then step(k+1,-p); end; end; begin a1,1:=3; a1,2:=3; step(1,-1); end. 第五次课深搜2 1、n2的棋盘，填 1n2个数，要求下比上大，左比右大。程序如下：var a:array0.11,0.11of integer; b:array0.200of boolean; n,s:integer; procedure print; var i,j:integer; begin for i:=1 to n d

23、o begin for j:=1 to n do write(ai,j:3); writeln; end; writeln(-); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 45 页 - - - - - - - - - readln; end; procedure try(x,y:integer); var i,j:integer; begin if (x=n+1) then begin inc(s);print;exit;end; if y=n+1 then t

24、ry(x+1,1)else begin j:=0; if (y=1)and(ax,y-1j) then j:=ax,y-1; if (x=1)and(jax-1,y)then j:=ax-1,y; for i:=j+1 to n*n-(n-x+1)*(n-y+1)+1 do if bi then begin ax,y:=i; bi:=false; try(x,y+1);bi:=true; end; end; end; begin readln(n); fillchar(b,sizeof(b),true); s:=0; try(1,1); writeln(s); end. 2、n*n 方阵中填号

25、，使得每行每列都有m 个（ mn then begin print;inc(s);exit;end; if ym then try(x+1,1) else for i:=ax,y-1+1 to n-m+y do begin ax,y:=i;bi:=bi+1; if (bi=m-(n-x) then try(x,y+1); bi:=bi-1; end; end; begin readln(n,m); s:=0; fillchar(b,sizeof(b),0); fillchar(a,sizeof(a),0); try(1,1); writeln(s); end. 3、中国盒 ” abababab

26、_ ” -” aaaa_bbbb ” ; 程序如下：var a:array1.1000of string10; i,j:integer; procedure print(k:integer); var i:integer; begin for i:=1 to k do writeln(ai); end; function nrep(k:integer):boolean; var 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 45 页 - - - - - - - - -

27、 i:integer; begin nrep:=false; for i:=1 to k-1 do if ai=ak then exit; nrep:=true; end; procedure try(k:integer); var i:integer; begin if ak-1=aaaa_bbbbthen begin print(k-1);exit;end; for i:=1 to 9 do if ak-1,i=_ then break; for j:=1 to 9 do if (j+1i+1) then begin ak:=ak-1; ak,i:=ak-1,j; ak,i+1:=ak-1

28、,j+1; ak,j:=_; ak,j+1:=_; if nrep(k) then try(k+1); end; end; begin a1:=abababab_; try(2); end. 第六次课深搜（）搜索：问题的表示、状态（初始状态-目标状态）、变化的规则。判合法、判重复、判结果最优解的求法：用一个变量去存放最优解，每次去比，搜一遍，挑一个最优的。角度：哪个角度的工作量最少，就从哪个角度去搜即搜的次数最少。次序：选择哪个次序，把最好的放在前面，把不好的放在后边。深度：深度为m，宽度为n，则搜索的次数为nm，所以尽量减少深度，把一些不可能的深度让其退出，就是优化。宽度：把无效的给滤掉。展

29、望：求最优解时适用。先把最优解给存起来，如果一个值明显比最优解不好，则让他退出，就是优化。、任务的最佳安排。源程序名arrange.?(pas|c|cpp) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 45 页 - - - - - - - - - 输入文件名arrange.in 输出文件名arrange.out 时间限制1s/testcase 空间限制32MB - 问题描述给省队选拔赛命题的时候，周老师手下有N 个命题人，要命N种不同类型的试题， 其中每人命每一类型

30、的试题一题。因为每个命题人对不同题型的掌握程度不同，所以他们编出的试题难度也有不同（这用一个难度数值来表示） 。为了尽可能地刁难大家，周老师决定出一张 N 个题的试卷，每一类型的试题一题， 而且所有题的难度值总和最大。- 输入数据第一行为 N(N = 20)，代表命题人的个数。（40% 的数据 N=10 ）以后 N行，每行 N 个整数（每个数不超过100 ） ，第 i 行 j 列的数表示第 i 个人出的第 j 种题目的难度大小。- 输出数据一行，表示试卷难度的最大值。- 样例输入3 50 50 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

31、 - - - - 名师精心整理 - - - - - - - 第 15 页，共 45 页 - - - - - - - - - 10 100 10 100 10 10 - 样例输出201 程序如下：var a:array1.20,1.20of integer; b:array1.20of boolean; d:array0.21of integer; max,n,i,j:integer; f:text; procedure step(x,s:integer); var i,j:integer; begin if s+dx+1n then if smax then begin max:=s; exi

32、t;end; for i:=1 to n do if bi then begin bi:=false; step(x+1,s+ax,i); bi:=true; end; end; begin assign(f,input.in); reset(f); readln(f,n); for i:=1 to n do begin for j:=1 to n do read(f,ai,j); readln(f); end; close(f); 加展望名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

33、第 16 页，共 45 页 - - - - - - - - - dn+1:=0; for i:=n downto 1 do begin di:=ai,1; for j:=2 to n do if ai,jdi then di:=ai,j; di:=di+di+1; end; max:=0; fillchar(b,sizeof(b),true); step(1,0); writeln(max); end. 、背包问题（ 01）要么装，要么不装，不允许切割。（1）设有一个背包可以放入的物品重量为V，现有 n 件物品，重量分别为 W1,W2,.Wn。 问能否从这 n件物品中选择若干件放入此背包，使得

34、放入的重量之和最接近或正好为V。 （不允许重复）变式：装箱问题问题描述有一个箱子容量为V（正整数， 0V20000） ，同时有 n 个物品（0n30，每个物品有一个体积（正整数） 。 （允许重放）要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。样例输入：24一个整数，表示箱子容量6一个整数，表示有n 个物品8接下来 n 行，分别表示这 n 个物品的各自体积312797输出：0一个整数，表示箱子剩余空间。 （要么为 0，要么为一个较小的数）程序如下 : 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

35、- - - - - - - 第 17 页，共 45 页 - - - - - - - - - uses dos; var a:array1.50 of integer; b:array0.50 of integer; v,n,min:integer; h,f,m,m1:word; procedure init; var f:text; i,j,k:integer; begin assign(f,10.txt); reset(f); readln(f,v); readln(f,n); for i:=1 to n do readln(f,ai); close(f); for i:=1 to n-1

36、do for j:=i+1 to n do if aiaj then begin k:=ai;ai:=aj;aj:=k;end; end; procedure try(k,s:integer); var i:integer; begin if smin then min:=s; if san then exit; for i:=bk-1+1 to n do if ai=s then begin bk:=i; try(k+1,s-ai); end; end; begin gettime(h,f,m,m1); writeln(h,:,f,:,m,:,m1); init; min:=v; b0:=0

37、; try(1,v); writeln(min); gettime(h,f,m,m1); writeln(h,:,f,:,m,:,m1); end.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 45 页 - - - - - - - - - 程序如下：、背包问题，求背包的价值值最大。?n 个物品重量和价值对应关系如图所示，求价值最大。三、采药(medic.pas/c/cpp) 【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望

38、的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“ 孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。 如果你是一个聪明的孩子， 你应该可以让采到的草药的总价值最大。 ” 如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件 medic.in的第一行有两个整数T（1 = T = 1000 ）和M（1 = M = 100 ） ，用一个空格隔开， T 代表总共能够用来采药的时间， M 代表山洞里的草药的数目。接下来的M 行每行包括两个在1 到 100 之间（包括 1

39、 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 45 页 - - - - - - - - - 【输出文件】输出文件 medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。【样例输入】70 3 71 100 69 1 1 2 【样例输出】3 【数据规模】对于 30%的数据， M = 10；对于全部的数据， M max then max:=s; if t1am+1,

40、1 then exit; for i:=bk-1+1 to m do if ai,1aI,1 then am+1,1:=aI,1; am+1,1 存放最小时间值 for i:=1 to m-1 do for j:=i+1 to m do if ai,2/ai,1aj,2/aj,1 then begin k:=ai; ai:=aj;aj:=k;end;max:=0; try(1,t,0); writeln(max); end.第七次课深搜（）一、 棋子控制棋盘的棋盘上的每棵棋子都可以控制它的上下左右不能放棋子，求可以控制整个棋盘的最少棋子数。名师资料总结 - - -精品资料欢迎下载 - - -

41、- - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 45 页 - - - - - - - - - const c:array1.5,1.2of integer=(0,1),(0,-1),(1,0),(-1,0),(0,0); var a,b:array0.6,0.6of integer; min:integer; procedure lookup(var x,y:integer); var i,j:integer; begin for i:=1 to 5 do for j:=1 to 5 do if ai,j=0 then b

42、egin x:=i;y:=j;exit; end; x:=0 end; procedure try(k:integer); var x,y,xx,yy,i,j:integer; begin if min0)and(xx0)and(yy6)then begin inc(axx,yy,10); for j:=1 to 4 do inc(axx+cj,1,yy+cj,2); try(k+1); for j:=1 to 4 do dec(axx+cj,1,yy+cj,2); dec(axx,yy,10); end; end; end; begin fillchar(a,sizeof(a),0); mi

43、n:=15; try(1); writeln(min); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 45 页 - - - - - - - - - end. inc(axx,yy,10); for j:=1 to 4 do inc(axx+cj,1,yy+cj,2); try(k+1); for j:=1 to 4 do dec(axx+cj,1,yy+cj,2); dec(axx,yy,10); end; end; end; begin fillchar(a,si

44、zeof(a),0); min:=8; try(1); writeln(min); end. 二、均分数据源程序名data.?(pas|c|bas) 输入文件名data.in 输出文件名data.out【问题描述】已知 N 个正整数： A1、A2 、 An 。今要将它们分成M 组（X1，X2， Xm ） ，使得各组数据的数值和最平均，即各组的和与各组和的平均值的差的绝对值的和最小。公式如下：X=（X1+X2+ +Xm） M Y=X1X X2 XXmXX 是各组数据和的平均值，i为第 i 组数据的数值和。即求所有分法中值的最小值。【输入文件】输入文件 data.in 包括：第一行是两个整数，表示

45、N,M 的值（ N 是整数个数， M 是要分成的组数）第二行有 N 个整数，表示A1、A2、 An。整数的范围是1-50。（同一行的整数间用空格分开）【输出文件】输出文件 data.out 包括一行，这一行只包含一个数，表示各组的和与各组和的平均值的差的绝对值的和的最小值(四舍五入后保留2 位小数 )。【样例】若输入文件data.in 中的内容为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 45 页 - - - - - - - - - 6 3 1 2 3 4 5 6

46、 则输出文件data.out 中的内容应为0 00 （1 和 6、2 和 5、3 和 4 分别为一组）【问题规模】50%的数据 2=N=10,M=2 100%的数据 M=N = 20 ，2=Mn then begin s:=0; for i:=1 to m do s:=s+abs(bi-p); if smin then min:=s; exit; end; for i:=1 to m do begin bi:=bi+ak; try(k+1); bi:=bi-ak; end; end; begin assign(f,data.in); reset(f); readln(f,n,m); for i

47、:=1 to n do read(f,ai); close(f); p:=0; for i:=1 to n do p:=p+ai; p:=p/m; min:=10000000; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 45 页 - - - - - - - - - fillchar(b,sizeof(b),0); try(1); assign(f,data.out); rewrite(f); writeln(f,min:4:2); close(f); end. 算

48、法二：以组为出发点，搜索它内部放的数。组内是无序的，各数之间是组合问题；组间也是无序的，也是组合问题。组的控制只须把未被使用的第一个数定为该组的第一个元素，以后元素按组合的方式搜索。var a:array1.100 of integer; n,m,i,s,j:integer; b:array1.100 of boolean; c:array1.30,1.100 of integer; f:text; x,y:real; procedure try(k,l,s,p:integer;t:real); var i:integer; begin if kt+abs(s-x) then y:=t+abs

49、(s-x); exit; end; if y=t+abs(p+s)/k-x)*k then exit; if l=1 then begin for i:=1 to n do if bi then begin bi:=false; ck,l:=i; try(k-1,1,s-ai,0,t+abs(p+ai-x); try(k,2,s-ai,p+ai,t); ck,l:=0; bi:=true; break; end; end else begin for i:=ck,l-1+1 to n do 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

50、 - - 名师精心整理 - - - - - - - 第 25 页，共 45 页 - - - - - - - - - if bi then begin bi:=false; ck,l:=i; try(k-1,1,s-ai,0,t+abs(p+ai-x); try(k,l+1,s-ai,p+ai,t); ck,l:=0; bi:=true; end; end; end; begin assign(f,data.in8); reset(f); readln(f,n,m); for i:=1 to n do read(f,ai); close(f); for i:=1 to n-1 do for j: