Двойная акция "11"? Используйте жадный алгоритм, чтобы победить его!

Java алгоритм
Двойная акция "11"? Используйте жадный алгоритм, чтобы победить его!

В последние годы, чтобы стимулировать потребление, продавцы по-разному запускали различные виды деятельности, и операционная электронная коммерция во главе с Dooduo показала нам бесконечный «потенциал» маркетинга. Нет, недавно догоняя Double 11, Лао Вантоу из магазина шаговой доступности в сообществе также запустил акцию «обмен пустых винных бутылок на вино».

Эта статья была включена в серию Github «Алгоритм обучения Xiaobai»:GitHub.com/VIP камень/Али…

Правила активности

Когда клиент покупает X бутылок вина, он может обменять Y пустых винных бутылок на новую бутылку вина.

намекать:

Значения X и Y следующие:

  • 1 <= X <= 100
  • 2 <= Y <= 100

Значение Y не является фиксированным и выбирается случайным образом.

Если вы выпьете вино из бутылки, бутылка станет пустой.

пожалуйста рассчитайтеСколько бутылок вина можно выпить.

Пример 1:

Ввод: X = 9, Y = 3

Выход: 13

Объяснение: Вы можете обменять 3 пустые винные бутылки на 1 бутылку вина. Таким образом, вы можете выпить до 9 + 3 + 1 = 13 бутылок вина.

Пример 2:image.png

Вход: X = 15, Y = 4

Выход: 19

Объяснение: Вы можете обменять 4 пустые винные бутылки на 1 бутылку вина. Таким образом, вы можете выпить до 15 + 3 + 1 = 19 бутылок.

Пример 3:

Ввод: Х = 5, Y = 5

Выход: 6

Пример 4:

Вход: X = 2, Y = 3

выход: 2

Идеи решения проблем

В этом вопросе есть две сложности: во-первых, не установлено (случайно), сколько пустых бутылок можно обменять на бутылку вина, во-вторых, вы можете продолжать участвовать в обменных мероприятиях после того, как обмененное вино будет выпито. Поэтому, исходя из выполнения этих двух условий, рассчитайте максимальное количество бутылок, которые вы можете выпить.

Может быть, некоторые друзья знают идею решения проблемы, увидев название этой статьи, Да, эта статья заключается в использовании «жадного алгоритма» для вычисления окончательного ответа. В то же время эта проблема также соответствует идее решения проблем жадного алгоритма, то есть, если у вас есть бутылка вина, вы можете обменять ее, и вы можете обменять столько, сколько сможете. .

как дела

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

Жадные алгоритмы особенно эффективны в задачах с оптимальной подструктурой. Оптимальная подструктура означает, что локальное оптимальное решение может определять глобальное оптимальное решение.Проще говоря, проблему можно решить, разложив ее на подзадачи, а оптимальные решения подзадач могут быть рекурсивными к оптимальному решению конечной задачи.

Каркас реализации жадного алгоритма

Начиная с первоначального решения задачи:

в то время как (может сделать один шаг к заданной общей цели)

{

Используйте допустимые решения, чтобы найти элемент решения допустимого решения;

}

Допустимое решение задачи формируется путем объединения всех элементов решения.

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

Далее мы будем использовать код для демонстрации конкретной реализации жадного алгоритма.

Реализация кода 1: жадный

Во-первых, мы сначала преобразуем глобальную проблему в локальную проблему: когда пустую бутылку можно заменить бутылкой вина, мы заменим бутылку вина, Код реализации выглядит следующим образом:

// 贪心1：用 + 和 - 实现
class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        // 最大酒瓶数
        int total = numBottles;
        // 有酒瓶就兑换
        while (numBottles >= numExchange) {
            // 执行一轮兑换
            numBottles -= numExchange;
            ++total;
            // 兑换一次多一个酒瓶
            ++numBottles;
        }
        return total;
    }
}

Разбор кода

Идеи реализации:

  1. сначала выпей все виноint total = numBottles;
  2. Когда пустых бутылок будет достаточно, поменяйте бутылку вина и выполните ее один разwhileпетля;
  3. В цикле количество пустых бутылок +1, количество напитков, которые можно выпить +1;
  4. Выполните следующую петлевую оценку.

Мы отправляем приведенный выше код в LeetCode, и результат выполнения выглядит следующим образом:image.png

Реализация кода 2: жадное улучшение

Приведенный выше жадный алгоритм представляет собой циклический обмен одной бутылки вина и одной бутылки вина.Можем ли мы каждый раз обменивать все пустые бутылки (максимальное значение, которое можно обменять), а затем снова пить обмененное вино, а затем переходить к в следующий раз обмен?

Ответ - да, нам нужно только использовать операции по модулю и остатку для его достижения Конкретный код выглядит следующим образом:

// 贪心 2：用 / 和 % 实现
class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        // 总酒瓶数
        int total = numBottles;
        // 有酒瓶就兑换
        while (numBottles >= numExchange) {
            // 最多可兑换的新酒
            int n = numBottles / numExchange;
            // 累计酒瓶
            total += n;
            // 剩余酒瓶(剩余未兑换 + 已兑换喝掉的)
            numBottles = numBottles % numExchange + n;
        }
        return total;
    }
}

Мы отправляем приведенный выше код в LeetCode, и результат выполнения выглядит следующим образом:image.png

Суммировать

Жадный алгоритм на первый взгляд кажется «сложным», но оказывается, что его очень просто реализовать. На самом деле то же самое и с «алгоритмом»: на первый взгляд это слово кажется сложным для очень высокого уровня, на самом деле это просто вид мышления и фиксированная «рутина» для решения определенной задачи, и никакой загадки нет.

Часто говорят, что хотя дорога и длинна, она придет; «Трудное» и «легкое» всегда относительны, ведь от «трудного» к «легкому» есть процесс постепенного просветления и роста.

Желаю вам расти понемногу каждый день и, наконец, покинуть мой личный WeChat: GG_Stone, чтобы общаться друг с другом и вместе добиваться прогресса.

Ссылки и благодарности

Lee TCO's-talent.com/problems/wow…

呜呜 .cn Блог на .com / Steven_ Ох есть ...

this.wikipedia.org/This-functions/%e8...

Подпишитесь на официальный аккаунт «Java Chinese Community», чтобы увидеть больше статей об алгоритмической графике.

Категории