我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:大丰收高手论坛 > 动态规划 >

动态规划经典模型之线性模型

归档日期:04-30       文本归类:动态规划      文章编辑:爱尚语录

  定期推送帐号信息学新闻,竞赛自主招生,信息学专业知识,信息学疑难解答,信息学训练营信息等诸多优质内容的微信平台,欢迎分享文章给你的朋友或者朋友圈!NOIP2018冬令营火热报名中!

  动态规划基本会出现在信息学比赛的各类考试中,理解动态规划,学会动态规划的思想对于信息学的同学们来说至关重要!

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

  思路1:贪心算法。总是跑得最快的人跑回来的话,那么他在每次别人过桥的时候一定得跟过去。但是,来看一组数据 四个人过桥花费的时间分别为 1 2 5 10,按照贪心算法答案是19,但是实际答案应该是17。

  我们先将所有人按花费时间递增进行排序,假设前i个人过河花费的最少时间为opt[i]。

  其中opt[i-1]是i-1个人在对岸最少时间,所以此时手电筒必定在对岸;T[1]是送手电筒回来的时间;T[i]是最后渡河时间。

  其中opt[i-2]是i-2个人在对岸最少时间,所以此时手电筒必定在对岸;T[1]是送手电筒回来的时间;T[i]是最后渡河时间(i为目前为止最后一个,所以必定比另一个人慢),第一个T[2]是送手电筒回来的时间;第二个T[2]是2和1一起渡河的时间。

  这两种最后情况其实对应的是:每个人可以选择与1一起渡河,也可以选择除1和2之外的一个人渡河。

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

  思路1:贪心算法。总是跑得最快的人跑回来的话,那么他在每次别人过桥的时候一定得跟过去。但是,来看一组数据 四个人过桥花费的时间分别为 1 2 5 10,按照贪心算法答案是19,但是实际答案应该是17。

  我们先将所有人按花费时间递增进行排序,假设前i个人过河花费的最少时间为opt[i]。

  其中opt[i-1]是i-1个人在对岸最少时间,所以此时手电筒必定在对岸;T[1]是送手电筒回来的时间;T[i]是最后渡河时间。

  其中opt[i-2]是i-2个人在对岸最少时间,所以此时手电筒必定在对岸;T[1]是送手电筒回来的时间;T[i]是最后渡河时间(i为目前为止最后一个,所以必定比另一个人慢),第一个T[2]是送手电筒回来的时间;第二个T[2]是2和1一起渡河的时间。

  这两种最后情况其实对应的是:每个人可以选择与1一起渡河,也可以选择除1和2之外的一个人渡河。

本文链接:http://quangdungfc.net/dongtaiguihua/121.html