連續(xù)郵資問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上連續(xù)郵資問題#include <iostream>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

2、m,int bestx);int main()int *bestx;int n = 5;int m = 4;cout<<"郵票面值數(shù):"<<n<<endl;cout<<"每張信封最多允許貼的郵票數(shù):"<<m<<endl;bestx=new intn+1;for(int i=1;i<=n;i+)bestxi=0;cout<<"最大郵資:"<<MaxStamp(n,m,bestx)<<endl;cout<<&quo

3、t;以后最優(yōu)解:"for(i=1;i<=n;i+)cout<<bestxi<<" "cout<<endl;return 0;void Stamp:Backtrack(int i,int r)/* *動態(tài)規(guī)劃方法算計數(shù)組y的值。狀態(tài)轉(zhuǎn)移程過： *慮考將xi-1參加等價類集S中，將會起引數(shù)組x *能貼出的郵資范圍變大，對S的影響是如果S中的 *郵票不滿m張，那就直一貼xi-1,直到S中有m張 *郵票，這個程過會生產(chǎn)很多不同的郵資，取能生產(chǎn) *最多不同郵資的用郵票起碼的那個元素 */for(int j=0;j<=xi-2*

4、(m-1);j+)if(yj<m)for(int k=1;k<=m-yj;k+)/k xi-1的重復(fù)次數(shù)if(yj+k<yj+xi-1*k)yj+xi-1*k=yj+k;/如果yr的值在上述動態(tài)規(guī)劃算運程過中已賦值，則yr<maxintwhile(yr<maxint)r+;if(i>n)if(r-1>maxvalue)maxvalue=r-1;for(int j=1;j<=n;j+)bestxj=xj;return;int *z=new intmaxl+1;for(int k=1;k<=maxl;k+)zk=yk;for(j=xi-1+1;

5、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;