文档介绍:-
. z.
摘要
当今科技迅速开展,运用计算机解决实际问题变得异常重要。尤其是运用计算机实现算法设计具要重大意义。算法设计与分析,其实可以解释为一种优化问题,一般是对可以利用计算底向上的方法计算出最优解;
根据计算最优值得到的信息,构造最优解。
算法设计
int main()
{
int num,i,j,k;
for(k=2;k<num;k++)
{
for(i=0;i<num-k;i++)
{
int mark=i+k;
for(j=i+1;j<mark;j++)
{
if(list[i][j]+list[j][mark]<list[i][mark])
{
list[i][mark]=list[i][j]+list[j][mark];
}
}
}
}
cout<<list[0][num-1];
return 0;
}
-
. z.
本课设中list[0][n-1]代表所用租金最少,n为游艇出租站的个数。List[i][j]表示从第i个游艇出租站到第j个游艇出租站的费用〔其中i<j〕。当list[i][j]+list[j][mark]<list[i][mark]时,list[i][mark]=list[i][j]+list[j][mark]。则递归方程为
list[0][n-1]=min{list[0][k]+list[k][n-1],list[0][n-1]}
算法实现与结果
程序代码:
*include <iostream>
*include <vector>
using namespace std;
int main()
{
int num,i,j,k,tmp;
cin>>num;
vector< vector<int> >list;
vector<int>line;
for(i=0;i<num-1;i++)
{
(line);
for(j=0;j<=i;j++) //在容器前面添加些0,从而使list[i][j]表示从第i个出租站到第j个出租站所需的金额
{ //同时也去除无效的表示,比方list[0][0]直接赋值为0,从而使后面的计算更方便
list[i].push_back(0);
}
for(j=i+1;j<num;j++)
{
cin>>tmp;
list[i].push_back(tmp); //从i+1个出租站到第j+1个出租站所需金额
}
}
for(k=2;k<num;k++) //从两个出租站开场,逐步计算每几个出租站之间的最优解,最终计算num-1个出租站合并的最优解
{
for(i=0;i<num-k;i++)
{
int mark=i+k;
for(j=i+1;j<mark;j++)
{
-
. z.
if(list[i][j]+list[j][mark]<list[i][mark]) //例如list[0][1]+list[1][2]<list[0][2],则改变list[0][2]的值
{
list[i][mark]=list[i][j]+list[j][mark];
}
}
}
}
cout<<list[0][num-1];
return 0;
}
。
如图1所示,含有3个游艇出租站,从出租站1到出租站2,3分别需要租金为5,15,从出租站2到出租站3需要租金为7,则运用动态规划法求解出从出租站1到