stamps.h

回溯算法中的连续邮资问题

#ifndef Stamp
#define Stamp

#include "iostream.h"

template <class T> class stamps
{
public:
	stamps(int nn,int mm,int *xx);
	~stamps();
	void Backtrack(int i,int r);
	void print();
private:
	int n,m,maxvalue,maxint,maxl;
	T *x,*y,*bestx;
};

template <class T> stamps<T>::stamps(int nn,int mm,int *xx)
{
	int maxll=1500;
	n=nn;
	m=mm;
	maxvalue=0;
	maxint=32767;
	maxl=maxll;
	bestx=xx;
	x=new T[n+1];
	y=new T[maxl+1];
	for(int i=0;i<=n;i++)
		x[i]=0;
	for(int j=1;j<=maxl;j++)
		y[j]=maxint;
	x[1]=1;
	y[0]=0;

}

template <class T> stamps<T>::~stamps()
{
	delete []x;
	delete []y;
}

template <class T> void stamps<T>::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(int h=x[i-1]+1;h<=r;h++)
		if(y[r-h]<m)
		{
			x[i]=h;
			Backtrack(i+1,r);
			for(int k=1;k<=maxl;k++)
				y[k]=z[k];
		}
		delete []z;
}

template <class T> void stamps<T>::print()
{
	for(int i=1;i<=n;i++)
		cout<<bestx[i]<<ends;
	cout<<endl;
	cout<<"最大连续邮资区间:"<<"[1,"<<maxvalue<<"]"<<endl;
}

#endif