回 帖 发 新 帖 刷新版面

主题:帮我解出这个题,加分30哦!!!

[em18]邮票问题:
在一个信封上,最多可贴3张邮票,要你设计4种面值不同的邮票,要能贴出1到R的连续值;
并使R的值达到最大。
[em18][em18][em18][em10][em10][em10]

回复列表 (共6个回复)

沙发

给你个通用的。。。
第一个输入的数是M张,
第二个输入的数是N种。

程序如下:
var
  a:array  [1..100]  of  integer;
  money:array  [1..2550]  of  integer;
  total,n,m,i:integer;


procedure  search(k,n,x:integer);
var  i:integer;
begin
  if  (n=0)or(k=0)  then  exit;
  for  i:=n  downto 0  do
        begin
           x:=x+a[k]*i;
           n:=n-i;
           money[x]:=money[x]+1;
           search(k-1,n,x);
           x:=x-a[k]*i;
           n:=n+i;
       end
end;

function maxlong:integer;
var  j,total,max:integer;
begin
j:=n*a[m];
max:=0;
repeat
   while  (money[j]=0)and(j>0)  do
      j:=j-1;
   total:=0;
   while  (money[j]>0)and(j>0)  do
     begin total:=total+1;j:=j-1 end;
   if  max<total then  max:=total   ;
until  j<=0;
maxlong:=max
end;

begin
  readln(m,n);
  for  i:=1  to  m  do  read(a[i]);
  total:=0;
  search(m,n,0);
  writeln(maxlong)
end.

回溯算法。。。

板凳

分析:显然,只有4种邮票面值互不相同,才有可能得到最大的R值.
    设4种邮票的面值为a<b<c<d.显然a只能取1;b的可能取值在a+1到3a+1之间;c的可能取值在b+1到3b+1之间;d的可能取值在c+1到3c+1之间.
    对a,b,c,d的每一种组合,分别计算满足题目要求的R值,其中使R取最大值的那一种组合,即是所求的结果.
    可以通过一个四重循环来确定由某个组合a,b,c,d可能得到的R值.设面值为a的邮票可以贴n1张(0<=n1<=3),面值为b的邮票可以贴n2张(0<=n2<=3-n1),面值为c的邮票可以贴n3张(0<=n3<=3-n1-n2),面值为d的邮票可以贴n4张(0<=n4<=3-n1-n2-n3).对满足条件
                n1+n2+n3+n4<=3
的每一组n1,n2,n3,n4,计算积之和
                sum=n1*a+n2*b+n3*c+n4*d
并将sum加入到集合S中(s初始值为空集).最后,检测1,2,3,...,n是否在集合s中,若n在s中,而n+1不在s中,则R=n.
program ch64;
const m=3;  {信封上最多可贴m张邮票}
var a,b,c,d:integer;
    R,Q,x1,x2,x3,x4:integer;
function number(a,b,c,d:integer):integer;  {确定由面值为a,b,c,d的4种邮票可得到的R值}
var n1,n2,n3,n4,sum,n:integer;
    s:set of 1..100;
begin
    s:=[ ];
    for n1:=0 to m do
     for n2:=0 to m-n1 do
      for n3:=0 to m-n1-n2 do
       for n4:=0 to m-n1-n2-n3 do
        if n1+n2+n3+n4<=m  {不超过m张}
        then begin
          sum:=n1*a+n2*b+n3*c+n4*d;  {得到一种邮资}
          s:=s+[sum];             {放入s集合}
             end;
    n:=1;
      while n in s do n:n+1;
      number:=n-1;              {返回最大的R值}
end;
begin
    a:=1; R:=0;
    for b:=a+1 to m*a+1 do
     for c:=b+1 to m*b+1 do
      for d:=c+1 to m*c+1 do
      begin
       Q:=number(a,b,c,d);
       if Q>R then
       begin
         R:=Q;
         x1:=a;x2:=b;x3:=c;x4:=d;
       end;
      end;
    writeln;
    write('4种票面值为:',x1:4,x3:4,x3:4,x4:4);
end.

3 楼

不好意思~这是我以前贴过的~

4 楼

太谢谢了,真是感谢啊,我是新手,做7天做不出,想不到有人一下做出来了,高手啊啊啊

5 楼

这 是书上的例题~呵呵~~

6 楼

晕~[em08]

我来回复

您尚未登录,请登录后再回复。点此登录或注册