Столбец алгоритма: жадный алгоритм

алгоритм

Уровень: ★☆☆☆☆

Теги: "алгоритм", "жадный", "жадный"
автор:MrLiuQ
Рассмотрение:Команда QiShare

Эта статья познакомит вас с жадным алгоритмом.

1. Введение

Жадный алгоритм, также известный как «жадный алгоритм». При решении проблемы всегда делайте то, что кажется лучшим в данный момент. (локальное оптимальное решение) То есть, без учета общей оптимальности, то, что он сделал, является лишь в некотором смыслелокальный оптимум. Жадный алгоритм не может получить общее оптимальное решение для всех задач, но он может дать общее оптимальное решение или общее оптимальное решение для широкого круга задач.Приблизительное решение. (Источник Энциклопедия 360)

Примечание. Жадный алгоритм — это высокопроизводительный алгоритм с низкой сложностью и простой в использовании.

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

2. Алгоритмическое мышление

«Основные проблемы второстепенным».

  • Сделайте большие вещи маленькими: большая проблема, найдя пересечение с подзадачами, разделит сложную проблему на несколько маленьких проблем;

  • Мелкие дела сокращаются: из мелких проблем находят суть принятия решений и определяют стратегию локального оптимального решения.

  • Вычисляя локальное оптимальное решение, получают глобальное оптимальное решение или приближенное решение.

Псевдокод выглядит следующим образом:

从问题的某一初始解出发
    while (能朝给定总目标前进一步) 
        do
            选择当前最优解作为可行解的一个解元素；
    由所有解元素组合成问题的一个可行解。

3. Проблема поиска сдачи

это запросОптимальным решениемПример жадного алгоритма.

Сценарий: Кассир, которому нужна сдача88Юань. Как внести сдачу, минимальное количество бумаги/монет.

Идея: Найдите по очереди самую большую банкноту, Например: изменить 88 юаней,¥88 = ¥50 + ¥20 + ¥10 + ¥5 + ¥1 * 3

# arr的每一位：分别对应100块、50块、20块、10块、5块、1块纸币。
arr = [0,0,0,0,0,0]

def change(money):
    while money >= 1:
        if money >= 100:
            money -= 100
            arr[0] += 1
        elif money >= 50:
            money -= 50
            arr[1] += 1
        elif money >= 20:
            money -= 20
            arr[2] += 1
        elif money >= 10:
            money -= 10
            arr[3] += 1
        elif money >= 5:
            money -= 5
            arr[4] += 1
        elif money >= 1:
            money -= 1
            arr[5] += 1

change(88)
print arr

Вывод результата:

4. Проблема рюкзака 0-1

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

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

  • Жадная стратегия 1: каждый раз брать то, что вы можете получить в данный моментнаиболее ценныйпродукт.
  • Жадная стратегия 2: каждый раз брать текущий веслегчайшийпродукт.
  • Стратегия поросенка 3: Каждый раз, когда вы принимаетеЛучшее соотношение цены и качествапродукт. (которыйцена/весТовар с наибольшей стоимостью)

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

Жадная стратегия 1: выберите товар с наибольшей стоимостью.

Обратный пример: Максимальный вес рюкзака w = 4 кг

товар цена масса
Товар А 3000 юаней 4kg
Товар Б 2000 долларов 3kg
Товар С 1500 юаней 1kg

По стратегии сначала выбираем товар А, потом уже можно не выбирать, а лучше выбирать товары В и С.

Жадная стратегия 2: выбирайте самый легкий продукт.

Как и в стратегии 1, возьмем контрпример: Максимальный вес рюкзака W = 4 кг

товар цена масса
Товар А 3500 юаней 4kg
Товар Б 2000 долларов 3kg
Товар С 1000 юаней 1kg

Согласно стратегии, сначала выбираем товар С, потом товар Б, но, очевидно, лучше выбрать А.

Жадная стратегия 3: Выберите продукты с высокой стоимостью.

Пример счетчика:

Максимальный вес рюкзака W = 4 кг

товар цена масса
Товар А 3500 юаней 3.5kg
Товар Б 3000 юаней 3kg
Товар С 1000 юаней 1kg

В это время соотношение цена-качество такое же.Предположим, что продукт A выбран первым, тогда очевидно, что продукты B и C лучше (потому что B и C в сумме 4000 юаней, в то время как единственный выбор A является всего 3500 юаней).

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

Следовательно, оптимальное решение задачи о рюкзаке 0-1 — стратегия ДП (динамическое программирование) будет вСледующая главапредставлять.

рекомендуемая статья:

iOS быстро реализует построение пейджингового интерфейса
Ротация интерфейса в iOS
Фрейм общих методов компоновки в iOS
Автоматическое изменение размера общих методов макета iOS
Ограничение общей макета iOS
StackView общих методов компоновки iOS
Масонство общих методов компоновки iOS
Автоматическая компоновка iOS UIButton на основе содержимого
Еженедельник странных танцев

Категории