連續(xù)郵資問(wèn)題

1、連續(xù)郵資問(wèn)題#include using namespace std;class Stampfriend int MaxStamp(int ,int ,int );private:void Backtrack(int i,int r);int n;/郵票面值數(shù)int m;/每張信封最多允許貼的郵票數(shù)int maxvalue;/以后最優(yōu)值int maxint;/大整數(shù)int maxl;/郵資上界int *x;/以后解int *y;/貼出各種郵資所需起碼郵票數(shù)int *bestx;/以后最優(yōu)解;int MaxStamp(int n,int m,int bestx);int main()int *b

2、estx;int n = 5;int m = 4;cout郵票面值數(shù):nendl;cout每張信封最多允許貼的郵票數(shù):mendl;bestx=new intn+1;for(int i=1;i=n;i+)bestxi=0;cout最大郵資:MaxStamp(n,m,bestx)endl;cout以后最優(yōu)解:;for(i=1;i=n;i+)coutbestxi ;coutendl;return 0;void Stamp:Backtrack(int i,int r)/* *動(dòng)態(tài)規(guī)劃方法算計(jì)數(shù)組y的值。狀態(tài)轉(zhuǎn)移程過(guò)： *慮考將xi-1參加等價(jià)類集S中，將會(huì)起引數(shù)組x *能貼出的郵資范圍變大，對(duì)S的影響

3、是如果S中的 *郵票不滿m張，那就直一貼xi-1,直到S中有m張 *郵票，這個(gè)程過(guò)會(huì)生產(chǎn)很多不同的郵資，取能生產(chǎn) *最多不同郵資的用郵票起碼的那個(gè)元素 */for(int j=0;j=xi-2*(m-1);j+)if(yjm)for(int k=1;k=m-yj;k+)/k xi-1的重復(fù)次數(shù)if(yj+kyj+xi-1*k)yj+xi-1*k=yj+k;/如果yr的值在上述動(dòng)態(tài)規(guī)劃算運(yùn)程過(guò)中已賦值，則yrmaxintwhile(yrn)if(r-1maxvalue)maxvalue=r-1;for(int j=1;j=n;j+)bestxj=xj;return;int *z=new intm

4、axl+1;for(int k=1;k=maxl;k+)zk=yk;for(j=xi-1+1;j=r;j+)xi=j;Backtrack(i+1,r);for(int k=1;k=maxl;k+)yk=zk;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.xi=0;for(i=1;i=maxl;i+)X.yi=maxint;X.x1=1