百分求教一个很老的算法---邮票问题
邮票问题背景：设想一个国家发行n种不同面值的邮票，并假定每封信上至多只允许贴m张邮票，对于给定的m和n值，写一个算法求出从邮资1开始在增量为1的情况下可能获得的邮资值的最大连续区域以及获得此区域的各种可能面值的集合。
代码写不写无所谓，是否能给出设计思想或流程图。
课程设计老师出的一道题，他告诉我们是奥赛的题，用什么动态优化法，不明白……
问题点数：100、回复次数：9Top
1 楼hanc（寒晨）回复于 2004-07-03 19:20:07 得分 0
自己顶。Top
2 楼hcj2002（流浪者·躬自厚而薄责于人 ）回复于 2004-07-03 19:31:53 得分 0
用枚举
个人认为，所谓的的优化也就是减少不必要的循环吧Top
3 楼o1n（小毛子）回复于 2004-07-03 19:32:31 得分 0
这个动态优化我还真不知道,对不起楼主帮不了你.
帮你顶一下吧.Top
4 楼oo（为了名副其实，努力学习oo技术ing）回复于 2004-07-03 19:33:31 得分 0
用数学方法
也许会有个简单的公式Top
5 楼SimonSui（！熵、焓、自由能！）回复于 2004-07-03 22:03:28 得分 0
动态优化？动态规划？DP?
挺容易的，我懒得写了，你把帖子转到专题开发-数据结构与算法那一版去会有很多高手回答的。Top
6 楼hanc（寒晨）回复于 2004-07-04 11:43:02 得分 0
还是无解？？Top
7 楼zzwu（未名）回复于 2004-07-04 15:51:28 得分 50
网上找得到现成源码:
设一国家发行n种不同面值的邮票，并且每封信至多允许贴m张邮票，对于给定的m,n值，写一个算法求出从邮资1开始在增量为一的情况下可能获得的邮资值的最大连续区域以及获得这个区域的各种可能面值的集合。如，当 n=4,m=5,若有面值为（1，4，12，21）的四种邮票，则邮资最大的连续区域为1到71。还有其他面值的四种邮票可组成同样大小的区域吗？
#define M 5
#define N 4
int Sum[200];
int T=1;
int J;
int cc[N];
int sign=1;
int A[M+1]={1},A1[M+1]={1};
check(int count)
{int s,i;
work(count);
for(i=1;;i++)
for(s=0;s<J;s++)
{
if(Sum[s]==i)
break;
if(s==J-1)
return i-1;
}
}
work(int count)
{int i;
int su=0;
if(sign==0)
{for(i=0;i<T;i++)
su+=A[cc[i]];
for(i=0;i<J;i++)
if(Sum[i]==su)
break;
if(i==J)
{Sum[J]=su;
J++;
}
return -1;
}
for(T=1;T<=N;T++)
dod(0,1,count);
}
dod(int j1,int i,int count)
{
if(i==T+1)
{sign=0;
work(count);
return 0;
}
for(j1=0;j1<M;j1++)
{cc[i-1]=j1;
dod(j1,i+1,count);
}
}
we(int count)
{int i,m,k;
J=0;
sign=1;
if(count==M)
{A[M]=check(count);
if(A[M]>A1[M])
for(i=0;i<M+1;i++)
A1[i]=A[i];
return 0;
}
k=check(count);
for(m=A[count-1]+1;m<k+2;m++)
{
A[count]=m;
we(count+1);
}
}
main()
{int i;
we(1);
for(i=0;i<M+1;i++)
printf("\t%d",A1[i]);
}
Top
8 楼kbsoft（让世界充满爱!）回复于 2004-07-04 16:52:49 得分 50
#define MAX 250
long i,kind,num,maxcontinue,s[10],result[10];
long d[MAX];
long continue(long d[])
{
long i,c=1;
while (d[c]<=num) c++;
return c;
}
void Search(long dep,long maxc,long d[])
{
long i,j,k;
long temp[MAX];
if (dep>kind)
if(maxc>maxcontinue) {
maxcontinue=maxc;result=s;}
else
for(i=s[dep-1]+1;i<=maxc;i++)
{
s[dep]=i;
temp=d;
for(j=1;j<num;j++)
for(k=0;k<=max-j*i;j++)
{
if(temp[k+j*i]>d[k]+j) temp[k+j*i]=d[k]+j;
if(num*i<=max) temp[num*i]=num;
Search(dep+1,continue[temp],temp);
}
}
}
void main()
{
scanf("%l\n",&num);
scanf("%l"\n",&kind);
//Init
s[1]=1;
for i:=1 to max do d[i]:=maxint;
for i:=1 to num do d[i]:=i;
d[0]=0; maxcontinue=0;
Search(2,continue[d[,d);
for(i=1;i<=kind;i++) printf("%l",result[i]);
printf("\n");
printf("MAX=%l",maxcontinue-1);
}
Top
9 楼langxiaofeng（流星）回复于 2004-07-04 19:38:16 得分 0
同意楼上UPTop
