Algorithm - Số lượng tối đa của hạt có thể được vận chuyển

Question

Tôi đã xem qua một câu hỏi phỏng vấn hỏi tại Google mà tôi không thể giải quyết:

Có một đống N hạt kg tại một ốc đảo nằm trong một khoảng cách D km đến một thị trấn. Các hạt cần phải được vận chuyển bởi một giỏ lạc đà có vị trí ban đầu là tại ốc đảo. Giỏ hàng có thể mang theo C kg ngũ cốc cùng một lúc. Lạc đà sử dụng các loại ngũ cốc làm nhiên liệu trong khi vận chuyển chúng. Nó tiêu thụ F kg/km.

Viết hàm tính toán số lượng ngũ cốc tối đa (X kg) có thể được vận chuyển đến thị trấn.

---

Tôi cố gắng để sử dụng đệ quy nhưng tôi không thể nhận được nhiều hơn nữa mà không gây nhầm lẫn bản thân mình.

Dưới đây là những gì tôi có cho đến nay:

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

Giả sử N, D, C và F là đầu vào, -

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

Là một ý tưởng, trong khi có nhiều hơn D * F hạt trong ốc đảo lạc đà sẽ đi du lịch, với C kg, hoặc tuy nhiên nhiều còn lại trong ốc đảo. Con lạc đà tiêu thụ D * F kg trên chuyến đi ở đó, giảm tải trọng của mình - 2 * D * F kg hạt và trả về nếu có đủ ngũ cốc để đảm bảo hành trình trở về.

Answer 3

Đây chỉ là phỏng đoán. Tôi không chắc chắn lắm.

Cho phép G (x) biểu thị số lượng hạt tối đa được chuyển đến một khoảng cách x từ nguồn. Sau đó

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

Bây giờ, G (0) = N và chúng ta cần phải tìm G (D) bằng cách sử dụng công thức trên.

Các max thứ hai hạn (F, G (x)% CF) biểu thị

1. F = khi anh ấy không quay trở lại để thu thập các hạt còn lại trong lần truy cập trước
2. G (x)% C - F = hạt còn lại trong lần truy cập cuối cùng và sau đó tiêu thụ F để quay lại điểm đến

Answer 4

Tôi nghĩ rằng vấn đề này được làm việc tốt nhất lặp đi lặp lại, tiến lên. Tôi sẽ chia ra các điểm quyết định. Nếu tôi viết một công thức, tôi sẽ sử dụng ?: Tất cả các kết quả đều bằng 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.