算法 - 能够运输

Question

谷物我碰到在谷歌提出的采访问题就来了，我解决不了的最大数量：

有一个在坐落在距离绿洲N千克粒一堆D公里到镇。谷物需要通过最初位于绿洲的骆驼手推车运输。购物车一次可携带C千克的谷物。骆驼在运输时使用谷物作为燃料。它消耗F千克/公里。

写一个函数，计算可以运输到城镇的最大数量的谷物（X千克）。

---

我试图用递归，但我无法得到更进一步不混淆自己。

这是我到目前为止有：

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); 
} 

Answer 2

这样的想法，同时还有比在绿洲的骆驼将前往d * F粒子多，用C千克，或不过多留在绿洲。骆驼在那里旅行时消费D * F kg，从他的负载下降 - 2 * D * F kg粮食，如果剩下足够的粮食以保证返程，则返回。

Answer 3

这只是一个猜测。我不完全确定。设G（x）表示从源头运输到距离x的最大谷物量。 然后

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

现在，G（0）= N，我们需要找到使用上述配方G（d）。

的第二项最大（F，G（X）％CF）表示

1. F =时，他不回来，收集剩余的谷物中 上次访问
2. G（X）％ C - F =上次访问中剩余的谷物，然后消耗F返回目的地

Answer 4

我认为这个问题最好是迭代地工作，转发。我将分解决策点。如果我正在写一个公式，我会用？：所有结​​果都以公斤为单位。

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.