算法 - 可以运输的最大谷物数量

Question

我遇到了Google提出的一个我无法解决的面试问题:

N在距离D城镇一公里的绿洲上有一堆千克谷物.谷物需要通过骆驼车运输,其初始位置在绿洲.推车一次可以携带C千克谷物.骆驼在运输时使用谷物作为燃料.它消耗Fkg/km.

写一个函数来计算X可以运送到城镇的最大谷物量(kg).

---

我试图使用递归但是如果不混淆自己,我就无法进一步发展.

这是我到目前为止所拥有的:

number of transports = N / C

fuel amount for distance D = D * F

X = N - ((number of transports) * 2 * (fuel amount for distance D))

Answer 1

假设 N、D、C 和 F 是输入，-

float computeMaxGrains(float N, float D, float C, float F)
{
    //Case when the cart can carry all grains at once
    if(N <= C)
    {
        float remainingGrains = N - D*F;
        if(remainingGrains >= 0)
        {
            return remainingGrains;
        }
        else
        {
            //out of fuel
            return 0;
        }
    }

    // Grains consumed per Km = (Total Number of Trips) * F
    // Total Number of Trips = 2*(N/C) + 1
    float grainsConsumedPerKm = (float) (2*(Math.floor(N/C)) + 1);

    // Remaining grains after Camels fuel = C*(N/C - 1)
    float remainingGrains = (float) (C*(Math.floor(N/C)));

    // Distance that the Camel is able to travel before the camel is 
    // 1 less round trip = 
    // (N - Remaining Grains) / grainsConsumedPerKm
    // From equation N - (grainsConsumedPerKm * distanceTravelled) = 
    // Remaining Grains
    float distanceTravelled = (N - remainingGrains) / grainsConsumedPerKm;

    if(distanceTravelled >= D)
    {
        return N - (D * grainsConsumedPerKm);
    }

    //Use recursion for every 1 less round trip
    return computeMaxGrains(remainingGrains, D-distanceTravelled, C, F);
}