Жадные алгоритмы - EcsFlash/DataTypes GitHub Wiki

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

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

Рассмотрим пример задачи о размере, которая постоянно встает перед миллионами кассиров во всем мире(как выдают сдачу)

Вот самое банальное решение этой задачи

if (n > 0)
{
	while (n >= five_thousand)
	{
		cout << five_thousand << " ";
		n -= five_thousand;
	}
	while (n >= two_thousand)
	{
		cout << two_thousand << " ";
		n -= two_thousand;
	}
	while (n >= one_thousand)
	{
		cout << one_thousand << " ";
		n -= one_thousand;
	}
	while (n >= five_hundred)
	{
		cout << five_hundred << " ";
		n -= five_hundred;
	}
	while (n >= two_hundred)
	{
		cout << two_hundred << " ";
		n -= two_hundred;
	}
	while (n >= one_hundred)
	{
		cout << one_hundred << " ";
		n -= one_hundred;
	}
	while (n >= fifty)
	{
		cout << fifty << " ";
		n -= fifty;
	}
	while (n >= ten)
	{
		cout << ten << " ";
		n -= ten;
	}
	while (n >= five)
	{
		cout << five << " ";
		n -= five;
	}
	while (n >= two)
	{
		cout << two << " ";
		n -= two;
	}
	while (n >= one)
	{
		cout << one << " ";
		n -=one;
	}
}