程序如下:
var
a:array[1..100,1..2]of integer; k:array[1..2]of integer; b:array[0..100]of integer; f:text;
t,m,max,i,j:integer;
procedure try(k,t1,s:integer); var
i:integer; begin
if s>max then max:=s; if t1
if a[i,1]<=t1 then begin b[k]:=i;try(k+1,t1-a[i,1],s+a[i,2]);end; end;
begin
assign(f,'medic1.in'); reset(f);
readln(f,t,m); for i:=1 to m do
readln(f,a[i,1],a[i,2]); close(f);b[0]:=0; a[m+1,1]:=a[1,1]; for i:=2 to m do
if a[m+1,1]>a[I,1] then a[m+1,1]:=a[I,1]; {a[m+1,1]存放最小时间值} for i:=1 to m-1 do for j:=i+1 to m do
if a[i,2]/a[i,1]
第七次课 深搜（４）
一、 棋子控制棋盘
５＊５的棋盘上的每棵棋子都可以控制它的上下左右不能放棋子，求可以控制整个棋盘的最少棋子数。
const
c:array[1..5,1..2]of integer=((0,1),(0,-1),(1,0),(-1,0),(0,0)); var
a,b:array[0..6,0..6]of 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 a[i,j]=0 then begin
x:=i;y:=j;exit; end; x:=0 end;
procedure try(k:integer); var
x,y,xx,yy,i,j:integer; begin
if min<=k-1 then exit; lookup(x,y);
if x=0 then begin min:=k-1;b:=a;exit;end; for i:=1 to 5 do begin xx:=x+c[i,1]; yy:=y+c[i,2];
if (xx>0)and(xx<6)and(yy>0)and(yy<6)then begin
inc(a[xx,yy],10); for j:=1 to 4 do
inc(a[xx+c[j,1],yy+c[j,2]]); try(k+1);
for j:=1 to 4 do
dec(a[xx+c[j,1],yy+c[j,2]]); dec(a[xx,yy],10); end; end; end; begin
fillchar(a,sizeof(a),0); min:=15; try(1);
writeln(min);
end.
inc(a[xx,yy],10); for j:=1 to 4 do
inc(a[xx+c[j,1],yy+c[j,2]]); try(k+1);
for j:=1 to 4 do
dec(a[xx+c[j,1],yy+c[j,2]]); dec(a[xx,yy],10); end; end; end; begin
fillchar(a,sizeof(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=｜X1－X｜＋｜X2－X｜＋……＋｜Xm－X｜
X是各组数据和的平均值，Ｘi为第i组数据的数值和。即求所有分法中Ｙ值的最小值。 【输入文件】
输入文件data.in包括：
第一行是两个整数，表示N,M的值（N是整数个数，M是要分成的组数）
第二行有N个整数，表示A1、A2、……、An。整数的范围是1--50。 （同一行的整数间用空格分开） 【输出文件】
输出文件data.out包括一行，这一行只包含一个数，表示各组的和与各组和的平均值的差的绝对值的和的最小值(四舍五入后保留2位小数)。
【样例】
若输入文件data.in中的内容为：
6 3
1 2 3 4 5 6
则输出文件data.out中的内容应为 0． 00
（1和6、2和5、3和4分别为一组） 【问题规模】
50%的数据2<=N<=10,M=2
100%的数据M<=N <= 20，2<=M<=5
算法一：
以每个数为出发点，搜索它放的组别。 var
a,b:array[1..20] of integer; n,m,i:integer; p,min:real; f:text; c:char;
procedure try(k:integer); var i:integer; s:real; begin
if k>n then begin
s:=0;
for i:=1 to m do s:=s+abs(b[i]-p); if s b[i]:=b[i]+a[k]; try(k+1); b[i]:=b[i]-a[k]; end; end; begin assign(f,'data.in'); reset(f); readln(f,n,m); for i:=1 to n do read(f,a[i]); close(f); p:=0; for i:=1 to n do p:=p+a[i]; p:=p/m; min:=10000000; fillchar(b,sizeof(b),0); try(1); assign(f,'data.out'); rewrite(f); writeln(f,min:4:2); close(f); end. 算法二： 以组为出发点，搜索它内部放的数。组内是无序的，各数之间是组合问题；组间也是无序的，也是组合问题。组的控制只须把未被使用的第一个数定为该组的第一个元素，以后元素按组合的方式搜索。 var a:array[1..100] of integer; n,m,i,s,j:integer; b:array[1..100] of boolean; c:array[1..30,1..100] of integer; f:text; x,y:real; procedure try(k,l,s,p:integer;t:real); var i:integer; begin if k<2 then begin if y>t+abs(s-x) then y:=t+abs(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 b[i] then begin b[i]:=false; c[k,l]:=i; try(k-1,1,s-a[i],0,t+abs(p+a[i]-x)); try(k,2,s-a[i],p+a[i],t); c[k,l]:=0; b[i]:=true; break; end; end else begin for i:=c[k,l-1]+1 to n do