6

我在谷歌遇到了一个我无法解决的面试问题：

N在距离城镇一公里的绿洲上有一堆公斤的谷物D。谷物需要由骆驼车运输，骆驼车的初始位置在绿洲。推车一次可以运载C公斤的谷物。骆驼在运输谷物时使用谷物作为燃料。它消耗F公斤/公里。

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))
4

4 回答 4

4

假设 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);
}
于 2012-11-19T18:49:51.873 回答
2

我认为这个问题最好迭代地工作，向前。我将拆分决策点。如果我正在编写一个公式，我会使用？：所有结​​果都以 Kg 为单位。

The first question is whether there is enough grain, and cart capacity, to 
justify an initial trip from oasis to town. The camel would eat FD, so 
if FD >= min(N,C) the answer is 0

If FD < min(N,C), the net amount transferred on the initial oasis to town 
trip is min(N,C)-FD. 

The camel is now in town, the remaining grain pile is N-min(N,C), and we 
have to decide whether to send it back again. If C <= 2FD, no round trip
can be profitable.

Otherwise consider a round trip with at least C remaining at the oasis. That 
gains net C-2FD (FD put in the cart in town to keep the camel fed getting 
to the oasis, C-FD remaining in the cart when it gets back to town).

If N>C, we can do floor((N-C)/C) of those round trips, net gain 
floor((N-C)/C)*(C-2FD).

After doing the initial run and any full cart round trips, the remaining 
grain pile is N%C, the remainder on dividing N by C.

If N%C > 2FD it is worth doing a final trip to empty the grain pile, with 
an additional net gain of N%C-2FD.
于 2012-11-19T09:27:38.747 回答
0

作为一个想法，虽然绿洲中有超过 D*F 的谷物，但骆驼会带着 C 公斤旅行，或者绿洲中还剩下多少。骆驼在那里的旅途中消耗了 D*F 公斤，卸下了他的负载 - 2*D*F 公斤的谷物，如果剩下足够的谷物来保证回程，它就会返回。

于 2012-11-19T03:09:58.057 回答
0

这只是一个猜测。我不确定。

令 G(x) 表示从源头运输到距离 x 处的最大谷物量。然后

G(x+1)= (G(x)/C)*(C-2F) + max(F,G(x)%C - F)

现在，G(0)=N，我们需要使用上述公式找到 G(D)。

第二项 max(F,G(x)%CF) 表示

  1. F = 当他上次访问没有回来收集剩余的谷物时
  2. G(x)%C - F =上次访问的剩余grain然后消耗F返回目的地
于 2012-11-19T08:56:42.923 回答