ダイナミックプランニング法ヨットレンタル問題C++コードを解く
10430 ワード
ダイナミックプランニング法はヨットのレンタル問題を解く
遊覧船のレンタル問題:長江観光クラブは長江の上でN個の遊覧船のレンタルステーション0を設置して、1、2、…、N-1、観光客はこれらの駅の中で遊覧船をレンタルして、そして下流のいかなる1つの遊覧船のレンタルステーションで返して、遊覧船のレンタルステーションiから遊覧船のレンタルステーションjの間の賃貸料はfee(i、j)で、0≦i
ダイナミックプランニング法を使用してヨットのレンタル問題を解き、問題モデルは「マルチソースポイントパス問題」であり、その核心はFloydアルゴリズムの使用である.
配列minCost[n][n]でサイト間の最低賃貸料を表し、fee[n][n]でサイト間の直通賃貸料を表し、minCost初期はfeeと等しいとする.動的計画関数を導出可能:minCost[i][j]=min{Fee[i][j],minCost[i][k]+minCost[k][j]}0≦k≦n-1
遊覧船のレンタル問題:長江観光クラブは長江の上でN個の遊覧船のレンタルステーション0を設置して、1、2、…、N-1、観光客はこれらの駅の中で遊覧船をレンタルして、そして下流のいかなる1つの遊覧船のレンタルステーションで返して、遊覧船のレンタルステーションiから遊覧船のレンタルステーションjの間の賃貸料はfee(i、j)で、0≦i
ダイナミックプランニング法を使用してヨットのレンタル問題を解き、問題モデルは「マルチソースポイントパス問題」であり、その核心はFloydアルゴリズムの使用である.
配列minCost[n][n]でサイト間の最低賃貸料を表し、fee[n][n]でサイト間の直通賃貸料を表し、minCost初期はfeeと等しいとする.動的計画関数を導出可能:minCost[i][j]=min{Fee[i][j],minCost[i][k]+minCost[k][j]}0≦k≦n-1
#include
using namespace std;
const int n = 6;
void Floyd(int arc[n][n], int dist[n][n]){
int i,j,k;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
dist[i][j] = arc[i][j]; // dist
for(k=0; k<n; k++)
for(i=0; i<n; i++)
for(j=0; j<n; j++)
if(dist[i][k]+dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k]+dist[k][j];
}
int main()
{
int fee[n][n]= {
{0,3,15,18,29,34},
{3,0,1, 17,18,23},
{15,1,0,10,12,15},
{18,17,10,0,4, 7},
{29,18,12,4,0, 1},
{34,23,15,7,1, 0}
};
int minCost[n][n];
Floyd(fee, minCost);
cout << " :" << minCost[0][5] << " 。"<< endl;
return 0;
}