首页 > 编程语言 > 详细

动态规划之线性模型之小朋友过河——Java实现

时间:2019-03-17 21:58:54      阅读:186      评论:0      收藏:0      [点我收藏+]

题目:

  在一个夜黑风高的晚上,有n(n <= 50)个小朋友在桥的这边,现在他们需要过桥,但是由于桥很窄,每次只允许不大于两人通过,他们只有一个手电筒,所以每次过桥的两个人需要把手电筒带回来,i号小朋友过桥的时间为T[i],两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

输入:

  有序数组(自定为有序,实际任意,数组内的数字代表对应索引过桥的时长)、数组长度

输出:

  累加最短的时间

实现:

public class 自底向上实现线性模型 {

    private static int minTime(int p[],int n){
        int opt[] = new int[n+1];
        for (int i = 0; i < n; i++) {
            opt[i] = p[i];
        }
        int minTime = 0;
        //  没有人的情况下
        if (n == 0)
            return 0;
        //  有一个人时,返回这个人的时间
        if (n == 1)
            return p[n-1];
        //  有两个人时,返回用时较多的人的时间
        if (n == 2)
            return Math.max(p[n-1],p[n-2]);
        /**
         * 人数多于2时,采用动态规划的思想,将问题拆分
         *  假设河的这一侧还剩一人,则派遣最快的人往返
         *  假设河的这一侧还剩二人,先派遣花费时间最少的人过来,待这两人走后,花费时间此少的人过来携带最少的人一同回去
         */
        for (int i = 2; i < n; i++) {
            opt[i] = Math.min(opt[i-1]+p[0]+p[i],opt[i-2]+p[0]+p[i]+2*p[1]);
            minTime = opt[i];
        }
        return minTime;
    }

    public static void main(String[] args) {
        System.out.println(minTime(new int[]{1,2,5,10,11},5));
    }

}

 

 

动态规划之线性模型之小朋友过河——Java实现

原文:https://www.cnblogs.com/zbb2161228/p/10549139.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!