计算机算法分析与设计（10）---租用游艇问题(含C++代码)

本文主要是介绍计算机算法分析与设计（10）---租用游艇问题(含C++代码)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

1、问题描述

 长江游艇俱乐部在长江上设置了 $n$ 个游艇出租站 $1,2,\dots \dots ,n$。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站 $j$ 之间的租金为$r(i,j)，1<=i<j<=n$。试设计一个算法，计算出从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

 输入格式：第 $1$ 行中有 $1$ 个正整数 $n（n<=200）$，表示有 $n$ 个游艇出租站。接下来的第 $1$ 到第 $n-1$ 行，第 $i$ 行表示第 $i$ 站到第 $i+1$ 站、第 $i+2$ 站、 … 、第 $n$ 站的租金。

 输出格式：输出从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

输入样例：
3
5 15
7
输出样例：
12

2、代码分析(用动态规划思路)

 1. 本题采用动态规划思路来解决，需要写出递归方程。

 2. 本题的思路和矩阵链相乘思路很相似，但递推方程不一样。租用游艇：比如从 $1$ 到 $3$，然后从 $3$ 到 $n$ ；矩阵链：比如从 $1$ 到 $3$，那么接下来就是 $4$ 到 $n$。

 3. 思路：中间位置划分：i -> k ->j。即分为 r[i][j] -> r[i][k] + r[k][j]。由于是最少租金，初始时 dp[i][j] = r[i][j]。状态转移方程为 dp[i][j] = min(dp[i][k] + dp[k][j]), k = [i+1 , j-1]。

时间复杂度 $O(n^3)$

#include<bits/stdc++.h>
using namespace std;
int main()
{int n, r[300][300], dp[300][300];cin >> n;for(int i = 1; i <= n; i++) //出租站i到i的租金为0 {r[i][i] = dp[i][i] = 0;}for(int i = 1; i <= n - 1; i++) //输入出租站i到i+1的租金 {for(int j = i + 1; j <= n; j++){cin >> r[i][j];dp[i][j] = r[i][j];}}for(int i = 1; i <= n - 1; i++){for(int j = i + 1; j <= n; j++){ for(int k = i + 1; k <= j - 1; k++){dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);}}}cout << dp[1][n];return 0;
} 

3、代码分析(用Dijkstra算法思路)

 1. 由于Dijkstra算法用于最短距离，所以这里我们用距离代替租金（本质是一样的）。

 2. 先用一个 $dis[j]$ 来存储站 $1$ 到站 $2$，站 $3$ … 站 $n$ 的最短距离，刚开始 $dis$ 的初始距离就是 $r[1][j]$ 的距离。

 3. 之后我们遍历查找确定其他的最小距离。因为前面 $1$，$2$ 已经确认所以我们从 i=3 开始，$j$ 从确定好的里面进行挑选，当 dis[i]>dis[j]+r[j][i] 时进行更新。最后输出 $dis[n]$。

时间复杂度 $O(n^2)$

#include<bits/stdc++.h>
using namespace std;
//这里用距离代替租金 
int main()
{int n;cin >> n;int r[n][n], dis[n];for(int i = 1; i <= n; i++) //出租站i到i的距离为0 {r[i][i] = 0;}for(int i = 1; i <= n - 1; i++) //输入出租站i到i+1的距离 {for(int j = i + 1; j <= n; j++){cin >> r[i][j];}}dis[0] = dis[1] = 0;for(int j = 2; j <= n; j++){dis[j] = r[1][j]; //dis的初始距离就是r[1][j]的距离}for(int i = 3; i <= n; i++){for(int j = 1; j <= i-1 ; j++){if(dis[i] > dis[j] + r[j][i]){dis[i] = dis[j] + r[j][i];}}}cout << dis[n];return 0;
} 

这篇关于计算机算法分析与设计（10）---租用游艇问题(含C++代码)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---