stamp.java

连续邮资问题,采用分支限界法编写,java实现

package zhanghan;
import java.io.*;
public class stamp {
	static int n,m,maxr,maxint,maxl;
	static int []x;
	static int []y;
	static int []bestx;
	public static int maxstamp(int nn,int mm,int []xx){
		int maxll=500;
		n=nn;
		m=mm;
		maxr=0;
		maxint=1000;
		maxl=maxll;
		bestx=xx;
		x=new int[n+1];
		y=new int[maxl+1];
		for(int i=0;i<=n;i++) x[i]=0;
		for(int i=1;i<=maxl;i++) y[i]=maxint;
		x[1]=1;
		y[0]=0;
		backtrack(2,1);
		return maxr;
	}
	public static void 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>maxr){
					maxr=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 j=x[i-1]+1;j<=r;j++)
			if(y[r-j]<m){
				x[i]=j;
				backtrack(i+1,r+1);
				for(int k=1;k<=maxl;k++)
					y[k]=z[k];
			}
	}
	public static void main(String a[]){
		int m=0;
		int n=0;
		int i=0;
		
		BufferedReader keyin=new BufferedReader(new InputStreamReader(System.in));
		try {
			
			System.out.println("请输入邮票种类：");
		     m=Integer.parseInt(keyin.readLine());
		 	System.out.println("请输入最多贴邮票张数：");
		     n=Integer.parseInt(keyin.readLine());	
		}
		catch (NumberFormatException e) 
		{
			e.printStackTrace();
		} 
		catch (IOException e)
		{
		
			e.printStackTrace();
		}
		int []best = new int [m];
		try {
		 	for(i=0;i<m;i++){
		 	System.out.println("请输入邮票面值"+i+":");
		 	best[i]=Integer.parseInt(keyin.readLine());
			}
		}
		catch (NumberFormatException e) 
		{
			e.printStackTrace();
		} 
		catch (IOException e)
		{
		
			e.printStackTrace();
		}
		for(i=0;i<m;i++){
		 	System.out.println(best[i]+best[i]);
		 	
			}
		
		maxstamp(m,n,best);
			
		
	}
	
}