砝码称重

现有1g、2g、3g、5g、10g、20g的砝码各若干枚，问用这些砝码可以称出多少种不同的重量。（设砝码的总重量不超过1000g，且砝码只能放在天平的一端）

要求：

输入方式：a1 a2 a3 a4 a5 a6

（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个） 输出方式：Total=N

（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不

用的情况）

如输入：1 1 0 0 0 0

则输出：TOTAL=3（表示可以称出1g，2g，3g三种不同的重量。） const

num:array[1..6]of byte=(1,2,3,5,10,20); {砝码的重量序列} var

a:array[1..6]of integer; {六种砝码的个数}

visited:array[0..1000]of boolean; {重量的访问标志序列}

no:array[0..1000]of integer; { no[0]—不同重量数；no[j]—第J种重量} total,i,j,k:integer; { total –目前称出的重量} begin

fillchar(visited,sizeof(visited),false);

for i:=1 to 6 do read(a[i]); {输入6种砝码的个数} no[1]:=0; no[0]:=1; {产生第一种重量0} for i:=1 to 6 do {阶段：分析第I种砝码}

for j:=1 to no[0] do {状态：穷举现有的不同重量}

for k:=1 to a[i] do {决策：在现有重量的基础上放K块第I种砝码} begin

total:=no[j]+k*num[i]; {产生一种新的重量}

if not visited[total] then {若该重量没产生过，则设访问标志} begin

visited[total]:=true;

inc(no[0]); {不同重量数加1}

no[no[0]]:=total; {新重量进入no 序列} end; end;

writeln(no[0]-1); {输出不同重量的个数—除去0} end.

参考程序2：（广度搜索） const

w:array[1..6] of byte=(1,2,3,5,10,20); {每种砝码的单位质量}

maxweight=1000; {最大质量，也是队列的最大长度} type twl=array[1..6] of integer; tlist=array[0..maxweight] of record

we:integer; {结点所对应砝码组合的总质量} sn:twl {每种砝码的个数} end; var a:tlist; {队列变量}

s:twl; {存放每种砝码的数量}

i:byte;

b:array[1..1000] of boolean; {标记某个质量是否可被称出}

head,tail：integer; {指针} cw:integer; begin

for i:=1 to 6 do read(s[i]);readln; {读入数据}

fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0); { a ，b 初始化} head:=0;tail:=0; {队列指针初始化} while head<=tail do {开始广度搜索} begin

for i:=1 to 6 do {试探每种砝码}

if a[head].sn[i]cw:=a[head].we+w[i]; { cw为新组合的总质量} if not b[cw] then begin {进队操作} inc(tail);

a[tail].we:=cw; b[cw]:=true;

a[tail].sn:=a[head].sn; inc(a[tail].sn[i]) end; end;

inc(head); {队首元素出队} end;

writeln('total=',tail); {输出结果} end.

测试数据：

编号 1 2 3 4 5

输入 200 100 30 20 20 10 2 2 0 0 0 0 1 0 3 0 0 0 3 4 0 5 0 0 2 2 2 2 2 2 输出 990 6 7 36 82 编号 6 7 8 9 0 输入 0 3 2 7 4 5 0 6 3 4 2 1 1 2 3 4 5 6 6 5 4 3 2 1 10 10 10 10 1 1 输出 185 79 204 83 140