haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

砝码称重

发布时间:2013-12-18 11:35:58  

砝码称重(动态规划)

现有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]<s[i] {新组合可以得到} then begin

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.

测试数据:

上一篇:单词接龙
下一篇:均分纸牌
网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com