连续邮资问题

连续邮资问题#includeiostreamusingnamespacestd;classStamp{friendintMaxStamp(int,int,int[]);private:voidBacktrack(inti,intr);intn;//邮票面值数intm;//每张信封最多允许贴的邮票数intmaxvalue;//以后最优值intmaxint;//大整数intmaxl;//邮资上界int*x;//以后解int*y;//贴出各种邮资所需起码邮票数int*bestx;//以后最优解};intMaxStamp(intn,intm,intbestx[]);intmain(){int*bestx;intn=5;intm=4;cout邮票面值数:nendl;cout每张信封最多允许贴的邮票数:mendl;bestx=newint[n+1];for(inti=1;i=n;i++){bestx[i]=0;}cout最大邮资:MaxStamp(n,m,bestx)endl;cout以后最优解:;for(i=1;i=n;i++){coutbestx[i];}coutendl;return0;}voidStamp::Backtrack(inti,intr){/**动态规划方法算计数组y的值。状态转移程过：*虑考将x[i-1]参加等价类集S中，将会起引数组x*能贴出的邮资范围变大，对S的影响是如果S中的*邮票不满m张，那就直一贴x[i-1],直到S中有m张*邮票，这个程过会生产很多不同的邮资，取能生产*最多不同邮资的用邮票起码的那个元素*/for(intj=0;j=x[i-2]*(m-1);j++){if(y[j]m){for(intk=1;k=m-y[j];k++)//kx[i-1]的重复次数{if(y[j]+ky[j+x[i-1]*k]){y[j+x[i-1]*k]=y[j]+k;}}}}//如果y[r]的值在上述动态规划算运程过中已赋值，则y[r]maxintwhile(y[r]maxint){r++;}if(in){if(r-1maxvalue){maxvalue=r-1;for(intj=1;j=n;j++){bestx[j]=x[j];}}return;}int*z=newint[maxl+1];for(intk=1;k=maxl;k++){z[k]=y[k];}for(j=x[i-1]+1;j=r;j++){x[i]=j;Backtrack(i+1,r);for(intk=1;k=maxl;k++){y[k]=z[k];}}delete[]z;}intMaxStamp(intn,intm,intbestx[]){StampX;intmaxint=32767;intmaxl=1500;X.n=n;X.m=m;X.maxvalue=0;X.maxint=maxint;X.maxl=maxl;X.bestx=bestx;X.x=newint[n+1];X.y=newint[maxl+1];for(inti=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(2,1);delete[]X.x;delete[]X.y;returnX.maxvalue;}