新建 文本文档 (2).txt

连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计,使得可在1张信封上贴出邮资1开始,增量为1的最大连续邮资区间

class Stamp { 
friend int MaxStamp(int,int,int[]); 
private: 
void Backtrack(int i,int r); 
int n, //邮资面值数 
m, //每张信封最多允许贴的邮票数 
maxvalue, //当前最优值 
maxint, //大整数 
maxl, //邮资上界 
*x, //当前解 
*y, //帖出各种邮资所需最少邮票数 
*bestx; //当前最优解 
} 


void Stamp::Backtrack(int i,int r) 
{ 
for(int j=0;j<=x[i-2]*(m-1);j++) 
if(y[i]<m) 
for (int k= 1;k<=y[j];k++) 
if(y[j]+k<y[j+x[i-1]*k])y[j+x[i-1]*k]=y[j]+k; 
while (y[r]<maxint)r++; 
if(i>n) { 
if(r-1>maxvalue){ 
maxvalue=r-1; 
for (int j= 1;j<=n;j++) 
bestx[j]=x[j];} 
return; 
} 
int *z=new int [maxl+1]; 
for (int k=1; k<=maxl; k++) 
z[k]=y[k]; 
for (int j = x[i-1]+1; j<=r; j++){ 
x[i] = j; 
Backtrack(i+1,r); 
for (int k = 1; k<=maxl; k++) 
y[k] = z[k];} 
delete []z; 
} 




int MaxStamp(int n, int m, int bestx[]) 
{ 
Stamp X; 
int maxint = 32767; 
int maxl = 1500; 
X.n=n; 
X.m=m; 
X.maxvalue=0; 
X.maxint=maxint; 
X.maxl=maxl; 
X.bestx=bestx; 
X.x=new int [n+1]; 
X.y=new int [maxl+1]; 
for (int i = 0; i<=n; i++) X.x[i]=0; 
for (int i = 1; i<=maxl; i++) X.y[i]=maxint; 
X.x[1] = 1; 
X.y[0] = 0; 
X.Backtrack(2,1); 
delete[] X.x; 
delete[] X.y; 
return X.maxvalue; 
}