Основная идея жадного алгоритма
1. Установите математическую модель, чтобы описать проблему.
2. Разделите решенные задачи на несколько подпрограмм.
3. Решите каждую подпроблема и получите локальное оптимальное решение в подпрограмме.
4. Синтезируйте локальное оптимальное решение подпространства в решение исходного решения проблемы.
Процесс реализации этого алгоритма:
Начиная с определенного начального решения проблемы;
Пока может перейти к данной общей цели
Найти элемент решения возможного решения;
Возможное решение проблемы состоит из всех элементов решения.
Жадная селективная природа
Так называемая природа жадного отбора означает, что общее оптимальное решение проблемы, которую вы ищете, может быть достигнуто с помощью ряда локальных оптимальных выборов. Текущая проблема без рассмотрения. Это первый основной элемент осуществимости жадных алгоритмов.
Жадные алгоритмы делают итеративно жадные варианты, и каждый раз, когда делается жадный выбор, проблема, которую вы ищете, уменьшается до меньшей подпроблемы.
Для конкретной проблемы, чтобы определить, имеет ли он жадный выбор выбора, необходимо доказать, что жадный выбор, сделанный на каждом шаге, в конечном итоге приводит к общему оптимальному решению проблемы.
2. Оптимальные свойства субструктуры <br /> Когда оптимальное решение проблемы содержит оптимальное решение ее субпроблемы, эта проблема, как говорят, обладает оптимальными субструктурными свойствами. Оптимальная природа субструктуры проблемы является ключевой функцией, которая может быть решена с помощью жадных алгоритмов.
Общий процесс жадности
Кода -копия выглядит следующим образом:
Жадный (c) // c - входной набор проблемы, то есть набор кандидатов
{
S = {};
В то время как (не решение (s)) // set s не представляет собой решение проблемы
{
x = select (c);
Если возможно (s, x) // Судите, является ли решение после добавления x в комплект S
S = s+{x};
C = c- {x};
}
возврат S;
Описание проблемы:
В настоящее время существуют монеты со значениями лица 2 Jiao 5 центов, 1 Jiao 5 центов, 5 центов и 1 цент.
Анализ проблем:
Согласно здравому смыслу, когда мы идем в магазин, чтобы купить вещи и найти деньги, босс всегда дает нам максимальную деноминацию в первую очередь. Если босс просит вас о результатах или нескольких центов, вы обязательно не сделаете этого. На самом деле, это типичная проблема жадного выбора.
Алгоритм проектирование и реализация проблемы :
Позвольте мне сначала привести вам пример. Он искал это? Не делайте этого, тогда босс может дать мне только 3 25 очков, и мне дали на 24 меньше, поэтому мне пришлось дать мне 2 10 очков и 4 1 балла.
Кода -копия выглядит следующим образом:
// арифметика для поиска изменений
// Вход: массив M, храните количество значений поверхности, расположенных от больших до малого.
// Вывод: массив NUM, сравните количество монет с различными значениями деноминации в массиве M и найдите денежный план
Public Static Int [] Zhaoqian (int m [], int n)
{
int k = m.length;
int [] num = new int [k];
для (int i = 0; i <k; i ++)
{
num <i> = n/m <i>;
n = n%m <i>;
}
вернуть num;
}
Кода -копия выглядит следующим образом:
Общественный класс Чжаоциан
{
Public Static Void Main (String [] args)
{
int m [] = {25,10,5,1};
int n = 99;
int [] num = new int [m.length];
num = zhaoqian (m, n);
System.out.println (n+«План установления денег:»);
для (int i = 0; i <m.length; i ++)
System.out.println (num <i>+"zip"+m <i>+"Значение лица");
}
Public Static Int [] Zhaoqian (int m [], int n)
{
int k = m.length;
int [] num = new int [k];
для (int i = 0; i <k; i ++)
{
num <i> = n/m <i>;
n = n%m <i>;
}
вернуть num;
}
}
Приведенное выше содержание этой статьи, я надеюсь, вам это может понравиться.