动态规划之游艇租赁(python实现)

动态规划之游艇租赁(python实现)

算法思想

动态规划也是一种分治思想，但与分治算法不同的是，分治算法是把原问题分解成若干子问题，自顶而下求解子问题，合并子问题的解，从而得到原问题的解。动态规划也是将原问题分解成若干子问题，然后自底向上，先求解最小的子问题，将结果存储在矩阵中，在求大的子问题时，直接从矩阵中查询小的子问题的解，避免重复计算。从而提高算法效率。
关键点：

• 最优子结构，是指原问题的最优解包含其子问题的最优解
• 子问题重叠，子问题重叠不是使用动态规划的必要条件，但是原问题存在子问题重叠更能体现动态规划的优势。

强烈推荐小白下载这个APP，快速搞懂算法运行流程。
算法动态图解：链接：
提取码：cv5y

样例：游艇出租

长江沿线共有n个游艇出租站，游客可以从每个出租站租游艇，并且能够在下游的任何一个游艇出租站归还。游艇出租站 i i i到下一站 j j j的租金用矩阵update_rent[i][j] 表示。设计一个算法，求解从出租站 i i i到出租站 j j j的最少租金并打印出对应的路线。

分析

• 1.分析最优解的结构特征

  • 假设我们已经知道在第 k k k个站点停靠会得到最优解，那么原问题就变成两个子问题:(i,i+1,…k),(k,k+1…j)之间的最少租金。
  • 那么原问题的最优解是否包含子问题的最优解呢？很显然是包含的。即最少租金 i i i-> j j j= i i i-> k k k+ k k k-> j j j

• 2.建立最优值的递归式
  当j=i时，只有1个站点，update_rent[i][j] = 0;
  当j=i+1时，只有2个站点，update_rent[i][j] = 1;
  当j>i+1时，有3个以上的站点，update_rent[i][j] = min(update_rent[i][k]+update_rent[k][j],update_rent[i][j]),i<k<j;

python实现

# coding=utf-8
# 初始化最大堆
import numpy as np# 1.初始化站点之间的租金，更新的租金和两地之间停靠点的indexinit_rent = np.array([[0,2,6,9,15,20],[0,0,3,5,11,18],[0,0,0,3,6,12],[0,0,0,0,5,8],[0,0,0,0,0,6]])
update_rent = py()
stop_arr = np.full((6,6),-1) # -1代表两个站点之间是直达的，中间没有停靠。# 2.按照递归公式进行计算
"""
当j=i时，只有1个站点，update_rent[i][j] = 0;
当j=i+1时，只有2个站点，update_rent[i][j] = 1;
当j>i+1时，有3个以上的站点，update_rent[i][j] = min(update_rent[i][k]+update_rent[k][j],update_rent[i][j]),i<k<j;
"""
def RentYacht(stops):"""返回起始站到终点站的最短距离:param stops::return:"""#1.判断站点数量if stops == 1:return 0elif stops == 2:return init_rent[0][1] # 直接返回两个站点之间的距离else:for d in range(2,stops): # 将问题分解为n-2个子问题for i in range(stops-d):j = i+dfor k in range(i+1,j): # 每个子问题的最优结果temp = update_rent[i][k] + update_rent[k][j]if temp<update_rent[i][j]:update_rent[i][j] = tempstop_arr[i][j] = kdef GetRoute(start = 0,end = 5):"""获取游艇的路线和最短距离，以0站点到5站点为例:param stop_arr::return:"""if stop_arr[start][end] == -1: #表示直达print("--{}".format(end),end="")returnGetRoute(start,stop_arr[start][end]) # 递归查找GetRoute(stop_arr[start][end],end)if __name__ == "__main__":RentYacht(6)print("初始化租金矩阵：n",init_rent)print("更新后的租金矩阵：n",update_rent)print("更新后的站点矩阵:n",stop_arr)print("从0站点到5站点，话费的最少租金为：{}".format(update_rent[0][-1]))print("最少租金经过的站点：0",end="")GetRoute()

复杂度分析

时间复杂度主要取决嵌套3层for循环，最坏情况为语句执行 O ( n 3 ) O(n^3) O(n3)。