连续邮资问题.cpp

经典算法之:连续邮资问题,全排列问题,有限期任务安排,整数划分问题,装载问题

#include<iostream.h>

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[j]<m)
			for(int k=1; k<=m-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(j=x[i-1]+1;j<=r;j++)
	{
		x[i]=j;
		BackTrack(i+1,r);
		for(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(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;
}

int main()
{
	int n,m;
	cout<<"请输入邮票面值数(n)和每张信封最多允许贴出的邮票数(m):";
	cin>>n>>m;
	int *bestx=new int [n+1];
	int maxvalue;
	maxvalue=MaxStamp(n,m,bestx);
	cout<<"最优解为: ";
	for(int i=1;i<=n;i++)
		cout<<bestx[i]<<"  ";
	cout<<"\n"<<"最大连续邮资区间为:"<<maxvalue<<endl;
	return 0;
}