Как я могу написать код Java, который решает эту проблему, используя жадный алгоритм проектирования?

Question

Проблема:

Вы отправляетесь в дальнюю поездку.Вы начинаете движение в 0-мильном посту. По пути есть n отелей, пронумерованных как 1 ≤ i ≤ n, в милевых столбах a 1

Кто-нибудь знает, как я могу написать код Java, который решает эту проблему с помощьюжадный алгоритм?

То, что у меня уже есть:

public static void greedy(int[] a) {
    int[] hotel = a;
    int[] cost = new int[hotel.length];
    int[] stop = new int[hotel.length];

    int dist = 0;

    for (int i = 0; i < hotel.length - 1; i++) {
        dist = a[i + 1] - a[i];
        cost[i] = (int) (Math.pow((200 - hotel[i]), 2));
        stop[i] = 0;
    }
}

Но я не знаю, куда идти отсюда ..

Answer 1

Насколько я понимаю, общее расстояние, которое вам нужно преодолеть, составляет a(n).Поскольку мы должны остаться в последнем отеле, то я хотел бы предложить жадное решение в обратном режиме.

Если a(n) - a(n-1) не может превышать 200 миль.Поэтому я хотел бы выбрать отель a(i), который находится в середине где-то между a(n) и a(n) - 200.Теперь, когда мы рассматриваем жадный подход, вам нужно выбрать этот отель и сохранить этот отель в вашем списке посещений.

Теперь идите вперед оттуда и выберите следующий отель, где расстояние находится между a(i) и a(i) - 200 и так далее, пока не дойдете до начальной точки.

Я не пишу код, так как полагаю, что это домашняя работа.Тем не менее, я думаю, вы поняли идею.Надеюсь, это поможет!Удачи.

Answer 2

Не пахать вперед и сразу начинать кодирование: начните с , анализируя задачу

Жадность означает взятьНаилучший возможный следующий шаг ( никогда оглядываясь назад; прогноз ограничен или запрещен).
Пусть dₓ будет расстоянием до дня x, и взглянем на отели на 150, 200, 250миль:
- если стоимость была 200-dₓ,
общая стоимость 150 с первым расстоянием 200, а также с 150
- если стоимость была (200-dₓ) ²,
общая стоимостьэто 22500 с первым расстоянием 200, только 12500 с 150:
лучше всего, когда каждая абсолютная разница максимально приближена ко всем остальным
- без (полного) прогнозированиявы не знаете все остальное:
следующее различие максимально близко к ожидаемое среднее оставшееся значение , насколько это возможно
- при прочих равных условиях вам лучшеменьше однодневных поездок, чем при большем
- с опережением 1, однодневная поездка стоимостью 50 и2500 становится опцией.

---

how I can write a Java code that solves this problem?
С жадным и повторным рассмотрением одного (более) примера (как всегда):

• не запишите алгоритм (пока):
• Дайте тестирование решение серьезной мысли
  Если не в анализе, это , где проблемы с определением задачи должны стать очевидными: 200 miles верхний предел?(Могу ли я сменить направление?)
  Зашифруйте тест, сделайте так, чтобы он проверял примерные задачи и результаты. Сделать так, чтобы он отмечал ошибочные результаты (, только).
• Только тогда начните набрасывать решение.
  Обычно я беру здесь обходной путь:
  Я запускаю исходный файл (или продолжаю тот, у которого есть тесты) и записываюописание задачи для выполнения с использованием соглашения о документации выбранного средства программирования с Java, которое будет комментарии документа .
  Я набросал решение синтаксически, поскольку комментарии в форме легко разделяются (Java: // строковые комментарии)
• проверить набросанное решение: предлагает ли какое-либо упрощение?
  Если оно выглядит сложным: можно ли снять ограничения, чтобы более простой подход дал такие же результаты?
  Этоможет в конечном итоге сэкономить время на реализацию этого подхода первым, даже если пересмотр ограничений отбросил результаты, отклонив его как решение.
  (Здесь предложение Даниэля стоило попробовать , если ваш подход выглядел значительно более сложным.)
• с понятным описанием что сделать как , вы готовы код

Answer 3

Этот вопрос программирования выглядит как школьное упражнение;вам, конечно, рекомендуется стараться изо всех сил ... в любом случае, вот несколько советов.

---

Сначала нам нужно выбрать жадный алгоритм, то есть алгоритм, основанный на некоторой эвристике, которая позволяет нам «оптимизировать» общую стоимость, основываясь на локально оптимальном выборе следующего отеля.(выбор будет выполняться на каждом этапе).

Таким образом, мы должны дать правило, применимое на каждом этапе, которое позволяет нам выбрать следующий отель.

В качестве локального оптимального выбора: мы могли бы выбрать, что каждый день мы движемся вперед, и если мы начнем с точки x, мы остановимся в следующем отеле, ближайшем к точке x+200.

В каком-то псевдокоде:

//start from 0
cost=0
position=0
while(position<end)
    //find the next best hotel h (based on the rule above)
    h=...
    //compute the daily_cost
    daily_cost=(h-position)^2
    //move to the selected hotel
    position=h
    //and increase the total cost:
    total_cost=total_cost+daily_cost

Когда position=end: мы прибыли, и мы вычислили total_cost на основе этого жадного алгоритма.