sellor.java

实现了《算法设计与分析》的一次课后题

import java.util.Scanner;

public class sellor {

	/**
	 * @param args
	 */
	private static int n;
	private static double[][]p; 
	public static void main(String[] args) {
		Scanner keyboard=new Scanner(System.in);//从键盘读入数据，计算结果输出到显示终端
		System.out.println("please input the number of points:");
		n=keyboard.nextInt();
		p=new double[n+1][2];
		System.out.println("please input"+n+"numbers:(include x and y index)");
		for(int i=1;i<=n;i++)
			for(int j=0;j<2;j++)
              p[i][j]=keyboard.nextDouble();
   System.out.println("the least distance is:"+solution(n));
	}
	public static double solution(int m)//动态规划求解最短路径
	{
		double[]s=new double[m+1];//数组s[i]存储第1个点到第2个，第2个到第3个...直到第i个点的距离之和
		double[]t=new double[m+1];//数组t[]存储最优值
		s[1]=0;
		for(int i=2;i<=m;i++)s[i]=dist(i-1,i)+s[i-1];
		t[2]=2*s[2];
		for(int i = 3;i<=m;i++){
			t[i]=t[2]+s[i]-2*s[2]+dist(1,i);
			for(int k=2;k<=i-2;k++){
				double temp=t[k+1]+s[i]+s[k]-2*s[k+1]+dist(k,i);
				if(t[i]>temp)t[i]=temp;
			}
		}
		return  t[m];
	}
	private static double dist(int i1, int i2) {//返回两点间的距离
		
		return Math.sqrt(Math.pow(p[i1][0]-p[i2][0],2)+Math.pow(p[i1][1]-p[i2][1],2));
	}
}