连续邮资(穷举法).cpp

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

#include <iostream.h>

void main()
{
	int a[5],b[2000];
	a[0]=1;
    int a0=1,p,max=0;
	for(int a1=a0+1;a1<=a0*4+1;a1++)
		for(int a2=a1+1;a2<=a1*4+1;a2++)
			for(int a3=a2+1;a3<=a2*4+1;a3++)
				for(int a4=a3+1;a4<=a3*4+1;a4++)
				{
					int s;
					for(int i=1;i<2000;i++)
						b[i]=0;
					for(int k0=0;k0<=4;k0++)
						for(int k1=0;k1<=4-k0;k1++)
							for(int k2=0;k2<=4-k0-k1;k2++)
								for(int k3=0;k3<=4-k0-k1-k2;k3++)
									for(int k4=0;k4<=4-k0-k1-k2-k3;k4++)
									{
										s=k0*a0+k1*a1+k2*a2+k3*a3+k4*a4;
										b[s]=1;
									}
									p=1;
									while(b[p++]==1);
									if(--p>max)
									{
										a[1]=a1;
										a[2]=a2;
										a[3]=a3;
										a[4]=a4;
										max=--p;
									}
				}
				for(int i=0;i<5;i++)
					cout<<a[i]<<ends;
				cout<<endl;
				cout<<max<<endl;
}