主题:连续邮票问题
shisutianxia
[专家分:630] 发布于 2007-10-20 12:48:00
输入(N,M),M为信封可贴的最大邮票数,N为邮票面值总数,求可贴出的最大邮票数
MAXVALUE并使得1...MAXVALUE的面值都能在邮票数不超过M时,用这些邮票贴出-----------初赛试题----求邮票面值设置
如(2,1)
面值设置---1,2,MAXVALUE 为2
如(2,2)
面值设置---1,2 MAXVALUE 为4(或1,3 MAXVALUE=4 当然只求一种方一种方案)
如(2,3)
面值设置---1,2 MAXVALUE为4
最后更新于:2007-10-20 14:26:00
回复列表 (共3个回复)
沙发
shisutianxia [专家分:630] 发布于 2007-10-20 16:52:00
子问题,拆分一个数
program chafen;
var m,n,i,j,lx:integer;d,x,rec:array[0..10]of integer;p:boolean;
procedure qiu(j,m:integer);
var i:integer;
begin
if m=0 then begin for j:=1 to x[0] do
d[j]:=x[j];d[0]:=x[0];p:=true;end else
if (j>0)and(m>0)then
if p=false then
for i:=0 to n do
begin
inc(x[0]);x[x[0]]:=rec[i];
qiu(j-1,m-rec[i]);
end;
x[0]:=x[0]-1;
end;
begin
writeln('m=');
readln(m);
writeln('n=');
readln(n);
fillchar(x,sizeof(x),0);
fillchar(rec,sizeof(rec),0);
fillchar(d,sizeof(d),0);
writeln('the vailable divided numbers -');
for i:=1 to n do
read(rec[i]);
write(' at most,use');
readln(j);
write('numbers');
x[0]:=0;rec[0]:=0;p:=false;readln;
qiu(j,m);
if p<>true then begin write('no solution');halt;end;
for i:=1 to d[0]-1 do
if d[i]<>0 then write(d[i],'+');
write(d[0]);
end.
板凳
shisutianxia [专家分:630] 发布于 2007-10-20 17:27:00
我的一个算法
program lianxuyou;
var bestx:array[0..100]of integer;
max,i,j,q,n,m,x:integer;p:boolean;
procedure panduan(j,m:integer);
var i:integer;
begin
if m=0 then p:=true else
if (j>0)and(m>0)then
if p=false then
for i:=0 to x do
begin
panduan(j-1,m-bestx[i]);
end;
end;
begin
readln(n,m);
bestx[0]:=0;bestx[1]:=1;x:=1;max:=1;
repeat
p:=false;
panduan(m,max+1);
if (x<=n)and p then max:=max+1;
if (x<n)and not(p) then begin inc(x);bestx[x]:=max;end;
until not(p)and(x=n);
writeln('maxvalue=',max);
for i:=1 to x do
write(bestx[i],'--');
end.
3 楼
封天怒龙 [专家分:160] 发布于 2007-10-21 14:00:00
这不是NOIP提高组的题目吗
我来回复