欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

租用游艇问题(暴力法/动态规划)

程序员文章站 2022-07-02 11:30:33
租用游艇问题导航问题描述:一、输入格式二、输出格式1.输入样例:2.输出样例:三、思路:1.暴力算法:2.动态规划:问题描述:长江游艇俱乐部在长江设置了n个游艇出租站1,2,…n,游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j) ,1<=i

租用游艇问题


问题描述:

       长江游艇俱乐部在长江设置了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

相关标签: 动态规划 算法