游艇租用问题的矩阵怎么算
答案:1 悬赏:30 手机版
解决时间 2021-03-14 02:15
- 提问者网友：心如荒岛囚我终老
- 2021-03-13 17:28
游艇租用问题的矩阵怎么算
最佳答案
- 五星知识达人网友：鱼芗
- 2021-03-13 17:49
对于题目课理解为，对于给定的游艇出租站i对游艇出租站j之间的租金为r（i，j），1≤i<j≤n，计算从游艇出租站1到游艇出租站n所需的最少租金。
将每个出租站看作一个点，站与站之间的关系可以用有向无环图表示，同时站与站之间的租金为边的权。
此问题可转化成求站1到站n的最短路径问题。
用动态规划求解，递推方程如下所示：定义f[i][j]为站点i到站点j的最少租金。
f[i][j] = min { f[i][k] + f[k][j] } i<k<j, 0<=i,j<=n-1
最少租金为：f[0][n-1]
将每个出租站看作一个点，站与站之间的关系可以用有向无环图表示，同时站与站之间的租金为边的权。
此问题可转化成求站1到站n的最短路径问题。
用动态规划求解，递推方程如下所示：定义f[i][j]为站点i到站点j的最少租金。
f[i][j] = min { f[i][k] + f[k][j] } i<k<j, 0<=i,j<=n-1
最少租金为：f[0][n-1]
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯