例2：在A、B两个城市之间设有N个路站(如下图中的S1，且N<100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数<=20，且每条路段上的距离均为一个整数)。
    A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，…最后到达B。通路上路段距离之和称为通路距离(最大距离<=1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。
    例如：下图所示是当N=1时的情况：

从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。

算法说明：本题采用穷举算法。
数据结构：N：记录A，B间路站的个数
          数组D[I，0]记录第I-1个到第I路站间路段的个数
              D[I，1]，D[I，2]，…记录每个路段距离
          数组G记录可取到的距离
程序清单：
program CHU7_6;
var i,j,n,s:integer;
  b:array[0..100] of integer;
  d:array[0..100,0..20] of integer;
  g:array[0..1000] of 0..1;
begin
  readln(n);
  for i:=1 to n+1 do
    begin
      readln(d[i,0]);
      for j:=1 to d[i,0] do read(d[i,j]);
    end;
  d[0,0]:=1;
  for i:=1 to n+1 do b[i]:=1;
  b[0]:=0;
  for i:=1 to 1000 do g[i]:=0;
  while        b[0]<>1       do
    begin
      s:=0;
      for i:=1 to n+1 do
        s:=       s+d[i,b[i]];     
        g[s]:=1;j:=n+1;
      while          b[j]=d[j,0]        do j:=j-1;
      b[j]:=b[j]+1;
      for i:=j+1 to n+1 do b[i]:=1;
    end;
  s:=0;
  for i:=1 to 1000 do
           s:=s+g[i];      
  writeln(s);readln;
end.

练习：

1。问题描述:将n个整数分成k组(k≤n,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,……sk,定义整数P为:

P=(S₁-S₂)²+(S₁一S₃)²+……+(S₁-S_k)²+(s₂-s₃)²+……+(S_k-1-S_k)²

问题求解:求出一种分法,使P为最小(若有多种方案仅记一种〉

程序说明:

数组:a[1],a[2],...A[N]存放原数

s[1],s[2],...,s[K]存放每个部分的和

b[1],b[2],...,b[N]穷举用临时空间

d[1],d[2],...,d[N]存放最佳方案

程序:

program exp4;

Var i,j,n,k : integer;

a :array [1..100] of integer;

b,d:array [0..100] of integer;

s :array[1..30] of integer;

begin

readln(n,k);

for I:=1 to n do read(a[I]);

for I:=0 to n do b[I]:=1;

cmin:=1000000;

while (b[0]=1) do

begin

    for I:=1 to k do   ①    

for I:=1 to n do

     ②    

sum:=0;

for I:=1 to k-1 do

for j:=   ③   

sum:=sum+(s[I]-s[j])*(s[I]-s[j]);

if    ④     then

begin

cmin:=sum;

for I:=1 to n do d[I]:=b[I];

end;

j:=n;

while     ⑤      do j:=j-1;

b[j]:=b[j]+1;

for I:=j+1 to n do     ⑥     

end;

writeln(cmin);

for I:=1 to n do write(d[I]:40);

writeln;

end.

2.问题描述:有n种基本物质(n≤10),分别记为P1,P2,……,Pn,用n种基本物质构造物品,这些物品使用在k个不同地区(k≤20),每个地区对物品提出自己的要求,这些要求用一个n

位的数表示:α₁α₂……αn,其中:

αi =1表示所需物质中必须有第i种基本物质

=-1表示所需物质中必须不能有第i种基本物质r

=0无所谓

问题求解:当k个不同地区要求给出之后,给出一种方案,指出哪些物质被使用,哪些物质不被使用。

程序说明:数组b[1],b[2],...,b[nJ表示某种物品

a[1..k,1..n]记录k个地区对物品的要求,其中:

a[I,j]=1表示第i个地区对第j种物品是需要的

a[i,j]=0表示第i个地区对第j种物品是无所谓的

a[i,j]=-1表示第i个地区对第j种物品是不需要的

程序:

program gxp2;

Var i, j ,k, n :integer;

p:boolean;

b :array [0..20] of 0..1;

a :array[1..20,1..10]d integer;

begin

readln(n,k);

for i:=1 to k do

begin

for j:=1 to n do read(a[i,j]);

readln;

end;

for i:=O to n do b[i]:=0;

p:=true;

while        ①       do

begin

j:=n;

while  b[j]=1 do j:=j-1;

    ②    

for i:=j+1 to n do b[I]:=0;

③

for i:=1 to k do

for j :=1to n do

if( a[i,j]=1 ) and (b[j]=0) or         ④      

then p:=true;

end;

if       ⑤    

then writeln('找不到!‘)

else for i:=1 to n do

if (b[i]=1) then writeln('物质',I,’需要')

else writeln('物质',i,'不需要');

end.