http://leetcode.com/2011/01/nuts-in-oasis-interview-question-from.html
http://www.cnblogs.com/yanyichao/p/3830559.html
http://www.cnblogs.com/oscarzhao/p/3629804.html
http://boke.name/beyondfeelings/2012/04/07/train_carrying_coal_problem_1/
若起点有n吨煤，运输k公里后，最多还剩多少吨？
Please read full article from http://leetcode.com/2011/01/nuts-in-oasis-interview-question-from.html
A pile of nuts is in an oasis, across a desert from a town. The pile contains ‘N’ kg of nuts, and the town is ‘D’ kilometers away from the pile.
The goal of this problem is to write a program that will compute ‘X’, the maximum amount of nuts that can be transported to the town.
The nuts are transported by a horse drawn cart that is initially next to the pile of nuts. The cart can carry at most ‘C’ kilograms of nuts at any one time. The horse uses the nuts that it is carrying as fuel. It consumes ‘F’ kilograms of nuts per kilometer traveled regardless of how much weight it is carrying in the cart. The horse can load and unload the cart without using up any nuts.
Your program should have a function that takes as input 4 real numbers D,N,F,C and returns one real number: ‘X’
double getMaxNuts(double N, double D, double C, double F) {
// base case:
// We have the capacity to carry all nuts,
// so fetch all the nuts in one trip
if (N <= C) {
double nutsAtDestination = N - D*F;
return (nutsAtDestination >= 0.0) ?
nutsAtDestination :
0.0; // out of fuel!
}
// # trips you would travel back and forth
int numTrips = 2*(ceil(N/C) - 1) + 1;
// how many nuts you consume per km
double costPerKm = numTrips * F;
// remaining weight of nuts after consumption
double remainingNuts = C*(ceil(N/C) - 1.0);
// this is the distance you are able to travel before you
// reach ONE LESS round trip fetching nuts
// derived from eq: N - costPerKm * traveled = remainingNuts
double traveled = (N - remainingNuts) / costPerKm;
// we are able to travel greater (or equal) than the remaining
// distance, so fetch the nuts right to the destination
if (traveled >= D)
return N - D*costPerKm;
// calculate recursively as we travel ONE less round trip now.
return getMaxNuts(remainingNuts, D-traveled, C, F);
}
火车运煤问题- 你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
- 很显然每次走全程的话是无法到达终点的，更别说剩余部分煤。必然把煤全部运到中间某点，然后再继续运
- 假设第一次把煤全部运输到中间某点A，距离为x，那么消耗的煤的数量为5x，因为要往返两次，再单程一次把剩下的1000吨运往A点。
- 如果A点剩余煤量3000-5x大于2000，那么下一次假设从A运输到B，距离为y，消耗的煤的数量同样是5y。
- 如果A点剩余煤量小于2000，那么从A到B只需往返一次，再单程一次，消耗煤的数量为3y。
- 由此可见，从一点到另外一点距离为s，中途不折返，如果初始煤量在3000~2000之间，需要消耗5s吨煤
- 同理得到，s距离不折返初始煤量在2000~1000之间，需要消耗3s吨煤
- s距离不折返初始煤量在1000~0之间，需要消耗s吨煤
- 那么最终的策略为每次选择单位消耗最小的方式运输，第一次消耗5x，第二次消耗3y，第三次消耗z。满足第一次消耗之后剩余2000吨，第二次消耗之后剩余1000吨
- x=200。转为单位消耗3的方式运输，y=333。转为单位消耗1的方式运输，z=（1000-x-y）= 467。剩余533吨煤
- 如果换一种思路，要求n1000吨煤最多可以运输多远，那么有n=1时为10001，n=2时为1000（1+1/3）。继续下去得到传输距离为1000(1+1/3+1/5+...+1/(2*n-1))。级数不收敛，表明只要煤足够多，能用运输到足够远
http://www.cnblogs.com/yanyichao/p/3830559.html
http://www.cnblogs.com/oscarzhao/p/3629804.html
http://boke.name/beyondfeelings/2012/04/07/train_carrying_coal_problem_1/
若起点有n吨煤，运输k公里后，最多还剩多少吨？
Please read full article from http://leetcode.com/2011/01/nuts-in-oasis-interview-question-from.html
