租用游艇问题(暴力法/动态规划)
问题描述:
长江游艇俱乐部在长江设置了n个游艇出租站1,2,…n,游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j) ,1<=i<j<=n,设计一个算法,计算出从出租站1到出租站n所需要的最少租金。
一、输入格式
第一行表示有n个站点,接下来n-1行是r( i , j)。
二、输出格式
输出最从游艇出租站1到出租站n所需的最少租金。
1.输入样例:
3
5 15
7
2.输出样例:
12
三、思路:
1.暴力算法:
很容易想到,我们可以用一个三重循环来遍历所有的选择,取最小的花费路线进行输出(num数组中读取输入的数据):
#include<bits/stdc++.h>
const int N = 1001;
using namespace std;
int n;
int num[N][N] = {0};
void readin(){
for(int i = 1; i <= n - 1; i++){
for (int j = i + 1; j <= n; j++)
cin >> num[i][j];
}
}
int deal_one(){
for(int r = 2 ; r <= n ; r++){
for(int i = 1 ; i <= n - r + 1 ; i++){
int j = i + r - 1;
for(int k = i ; k <= j ; k++)
num[i][j] = min(num[i][j] , num[i][k] + num[k][j]);
}
}
return num[1][n];
}
int main(){
cout << "请输入出租站个数:\n";
cin >> n;
readin();
cout << "暴力:\n";
cout << deal_one();
}
2.动态规划:
1.我们容易发现,在上面的方法中,存在着很多可以优化的地方:比如说我们这道题目问的是从1 到 n 的最小花费,所以说我们可以设置一个dp数组,用dp[ i ]来表示从 1 到 i 的最优解。我们找到从 1 到 i 的最优解之后,我们要得到从 1 到 n 的最优解,只需要改变 i 的值来对比即可。显然我们用一个N的空间来换取了
n
3
n^3
n3 到
n
2
n^2
n2转变的时间复杂度。
2.状态的定义:
dp[ i ]表示从1 到 i 我们的最优选择;
3.状态转移方程:
dp[i] = min(dp[i] , dp[j] + dp[j] + num[j][i]);
代码如下:
#include<bits/stdc++.h>
const int N = 1001;
using namespace std;
int n;
int num[N][N] = {0};
int dp[N] = {0};
void readin(){
for(int i = 1; i <= n - 1; i++){
for (int j = i + 1; j <= n; j++) cin >> num[i][j];
}
}
int deal_two(){
dp[1] = 0;
dp[2] = num[1][2];
for(int i = 3 ; i <= n ; i++){
dp[i] = num[1][i];
for(int j = 2 ; j <= n ; j++){
dp[i] = min(dp[i] , dp[j] + num[j][i]);
}
}
return dp[n];
}
int main(){
cout << "请输入出租站个数:\n";
cin >> n;
readin()
cout << "暴力:\n";
cout << deal_one();
cout << "\nDP:\n";
cout << deal_two();
}
本文地址:https://blog.csdn.net/qq_31747473/article/details/109234532
上一篇: 移动端常见问题(动画演示)
下一篇: 准备转行web前端,该怎么从头学好?