本文共 1768 字，大约阅读时间需要 5 分钟。

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){//当前的邮票是x[i],r是x[1- i-1]邮票所能表示的最大的连续上界    int j;    int k;    for(int j=0; j<=x[i]*(m-1); j++)        if(y[j]
   
    =n)    {        if(r>maxvalue)        {            maxvalue=r;            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(j=x[i]+1;j<=r+1;j++)//下一个区间的取值范围从[r+1,...],所以必须保证有值能取到r+1，因为这个区间能取到的最大连续值是r    {        if (y[r+1 - j] < m)        {            x[i+1]=j;            BackTrack(i+1,r);//r代表当前区间能取到的最大连续值            for(k=1;k<=maxl;k++)                y[k]=z[k];        }            }    delete [] z;}int MaxStamp(int n, int m, int bestx[]){    int i;    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(i=1;i<=maxl;i++)        X.y[i]=maxint;    X.x[1]=1;    X.y[0]=0;    X.BackTrack(1,0);//这样取值比王晓东书上的更好理解了，0前一个区间能取到的最大连续值是0，这是因为前一个区间没有任何邮票的面值    delete [] X.x;    delete [] X.y;    return X.maxvalue;}int main(){    int n,m;   // cout<<"请输入邮票面值数(n)和每张信封最多允许贴出的邮票数(m):";    while(scanf("%d%d",&n,&m))    {        int *bestx=new int [n+1];        int maxvalue;        maxvalue=MaxStamp(n,m,bestx);        cout<<"最优解为: ";        for(int i=1;i<=n;i++)            cout<
    
     <<"  ";        cout<<"\n"<<"最大连续邮资区间为:"<
     
      <
     
    
   

转载地址：http://mveti.baihongyu.com/