游艇租赁（车票选择）

游艇租赁（车票选择）"/>

游艇租赁（车票选择）

package sort;

/**
 * 游艇租赁最少费用计算：A点-B点,中途有1,2,3,4,5,6个停靠站点;每两个站点有不同的收费，计算任意两个站点最优方案及计算金额
 * （1,2）-2￥,（1,3）-6￥,（1,4）-9￥,（1,5）-15￥,（1,6）-20￥
 * （2,3）-3￥,（2,4）-5￥,（2,5）-11￥,（2,6）-18￥
 * （3,4）-3￥,（3,5）-6￥,（6,6）-12￥
 * （4,5）-5￥,（4,6）-8￥
 * （5,6）-6￥
 * 思路：假设i点到j点会在k点停靠是最优解,将路程分为(i,i+1,i+2,...,k),(k,k+1,...,j),即可以分为子序列,不断的拆解子序列
 * 最终会计算i和j相差2个站点,i和j相差3个站点,i和j相差4个站点的最优解之和
 * 当i=j m[i][j]=0;
 * 当j=i+1 m[i][j]=r[i][j],r[i][j]是两个站点的票价
 * 当j>i+1 m[i][j]=min{m[i][k]+m[k][j],r[i][j]}(i-k-j的票价之和和，i-j的票价取最小值)
 * 定义二维数组：r[i][j]是各个站点之间票价,m[i][j]计算个点之间的最小费用,s[i][j]记录两点之间停靠的站点
 * @author fengbin
 */
public class MinMoney {
    
    //站点的个数
    public static int n=6;
    public static int ms=7;
    public static int[][] r=new int[ms][ms],m=new int[ms][ms],s=new int[ms][ms];
    
    static void rent() {
        int i,j,k,d;
        for (d = 3; d <=n; d++) { //将问题分为小规模d
            for (i= 0; i <=n-d+1; i++) {
                j=i+d-1;
                for (k= i+1; k<j; k++) {
                    int temp;
                    temp=m[i][k]+m[k][j];
                    if(temp<m[i][j]) {
                        m[i][j]=temp;
                        s[i][j]=k;
                    }
                }
            }
        }
    }
    /**
     * 打印最短路线
     * @param i
     * @param j
     */
    public static void print(int i,int j) {
        if(s[i][j]==0) {
            System.out.print("--"+j);
            return;
        }
        print(i,s[i][j]);
        print(s[i][j],j);
    }
    /**
     * 打印二维数组
     * @param arr
     */
    public static void printArr(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            int[] temp = arr[i];
            for (int j = 0; j < temp.length; j++) {
                System.out.print(temp[j]+"\t");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        System.out.println("请输入站点的个数n:");
        System.out.println("请依次输入各站点之间的租金:");
        //代替一个个数字输入
        int[] in=new int[] {2,6,9,15,20,3,5,11,18,3,6,12,5,8,6};
        int index=0;
        for (int i = 1; i <n; i++) {
            for (int j = i+1; j <=n; j++) {
                r[i][j]=in[index];
                index++;
                m[i][j]=r[i][j];
                s[i][j]=0;
            }
        }
        //初始各个站点
        for (int i = 0; i < ms; i++) {
            for (int j = 0; j <ms; j++) {
                if(i==0 && j<ms) {
                    //设置6个点
                    m[i][j]=j;
                    s[i][j]=j;
                    r[i][j]=j;
                }
                if(j==0 && i<ms) {
                    //设置6个点
                    m[i][j]=i;
                    s[i][j]=i;
                    r[i][j]=i;
                }
            }
        }
        printArr(m);
        rent();
        System.out.println("s[i][j]记录两点之间停靠的站点:");
        printArr(s);
        System.out.println("花费的最少租金为："+m[1][n]);
        System.out.println("花费最少租金经过的站点:");
        print(1,n);
    }
       
}