topcoder上的一道算法题：
Problem Statement
The Breguet range equation tells us how far an aircraft can fly if it has a given mass of fuel on board. It states that the maximum range of an aircraft R is given by: R = K * ln(take-off mass / empty mass) where K is a constant for the aircraft and the take-off mass is equal to the empty mass + the mass of fuel on board the aircraft. In addition, taking off and gaining altitude takes a certain, constant amount of fuel. An airline wishes to minimize the amount of fuel consumed on a given journey by allowing the aircraft to stop at intermediate cities along the way to refuel. Assume that the aircraft can stop an unlimited number of times and can stop at any point of its journey. Also assume that it can carry an unlimited amount of fuel. You will be given an int distance, the total distance of the journey, the int value K for the aircraft, an int emptyMass containing the empty mass of the aircraft and an int takeoffFuel containing the additional mass of fuel required each time the aircraft takes off. You should return a double containing the minimum amount of fuel required to complete the journey.
Definition
Class:
FlightScheduler
Method:
minimizeFuel
Parameters:
int, int, int, int
Returns:
double
Method signature:
double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel)
(be sure your method is public)
Notes
-
The return value must be accurate to within an absolute or relative tolerance of 1e-9.
Constraints
-
distance will be between 1 and 200,000, inclusive.
-
K will be between 1 and 200,000, inclusive.
-
emptyMass will be between 1 and 200,000, inclusive.
-
takeoffFuel will be between 1 and 200,000, inclusive.
Examples
0)
40000
100000
150000
5000
Returns: 76420.82744805096
The optimal schedule here is to make 1 stop right in the middle of the flight.
1)
40000
55000
150000
5000
Returns: 138450.61724934017
K is a measure of the efficiency of the aircraft. With this less efficient aircraft it 's best to stop twice.
2)
1000
500
1000
50
Returns: 2664.9853821314487
3)
10000
100
200
5
Returns: 24635.869665316768
4)
140000
4
10000
10
Returns: 3.6576871282155204E8
//code:
#include <map>
#include <set>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cctype>
#include <list>
#include <iomanip>
#include <sstream>
using namespace std;
class FlightScheduler
{
public:
double F(int distace,int K,int emptyMass,int takeoffFuel,int n);
double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel);
};
double FlightScheduler::F(int distace,int K,int emptyMass,int takeoffFuel,int n)
{
if(n <=0)
return -1;
double answer=(emptyMass*(exp((double)distace/(n*K))-1)+takeoffFuel)*n;
if(answer <0)
return -1;
return answer;
}
double FlightScheduler::minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel)
{
//binary search
double x=1;
double right=(double)takeoffFuel/(double)emptyMass-1;
while((x-1)*exp(x) <right)
x=x*2;
x=(x+1)*2;//prevent some careless error
cout < <x < <endl;
//limit checked,start searching
double upper=x;
double lower=0;
while(upper-lower> 1e-9)
{
double middle=(upper+lower)/2;
double temp=(middle-1)*exp(middle);
if(temp> right)
upper=middle;
else
lower=middle;
}
cout < < "upper= " < <upper < <endl;
cout < < "lower= " < <lower < <endl;
//look for the correct n
double minFuel=F(distance,K,emptyMass,takeoffFuel,1);
for(int n=(int)(1/upper*distance/K-1000);n <=1/upper*(double)distance/(double)K+1000;n++)
{
double temp=F(distance,K,emptyMass,takeoffFuel,n);
if(temp <0)
continue;
if(temp <minFuel)
minFuel=temp;
}
cout < <endl < < "minFuel= " < <minFuel < <endl;
return minFuel;
}
void main()
{
FlightScheduler f;
f.minimizeFuel(40000,100000,150000,5000);
}
高手能不能帮忙解释一下该算法的代码。
非常感谢！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
[解决办法]
就是用解方程得方法求了一个近似的解，
然后再近似解得一个区间里找一个最优的
