Жадный алгоритм python пример

Русские Блоги

Алгоритм Python — жадный алгоритм для решения задачи о рюкзаке 0-1

оглавление

Жадный алгоритм и задача о рюкзаке 0-1

Решение задачи о ранце 0-1 с помощью жадного алгоритма является классической проблемой в мире алгоритмов.Автор попытался использовать скрипт на языке Python для получения соответствующих оптимальных результатов для входных данных задачи.

как поживаешь

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

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

Основная идея дизайна жадного метода состоит из трех этапов:
(1) Создайте математическую модель, которая точно описывает проблему, включая модель, определяющую оптимальное решение.
(2) Разбейте проблему на серию подзадач и определите оптимальную структуру решения подзадач.
(3) Примените жадный принцип для определения локального оптимального решения каждой подзадачи и суммируйте глобальное оптимальное решение с локальным оптимальным решением подзадач в соответствии с моделью оптимального решения.

Определение модели оптимального решения и определение оптимальной структуры решения подзадач обычно выполняются одновременно.Модель оптимального решения обычно отражает структуру декомпозиции и режим суммирования подзадач оптимального решения. Существует множество способов декомпозиции подзадач. Некоторые проблемы можно декомпозировать шаг за шагом в соответствии с процессом решения проблемы. На каждом шаге выбирается лучшее решение на основе предыдущего шага, и задача упрощается до Для меньшей проблемы, когда завершен последний шаг решения, получается глобальное оптимальное решение. Есть и другие проблемы, которые можно разложить на несколько относительно независимых подзадач, и после решения каждой подзадачи они объединяются в соответствии с определенными правилами для получения глобального оптимального решения.

0-1 задача о ранце

Есть N предметов и рюкзак с грузом C, каждый предмет весит w_i, Значение p_i, Решите, какие предметы упаковать в рюкзак, чтобы сумма веса этих предметов не превышала C, общее значение максимума.
Задача о рюкзаке — это общий термин для этого типа задач комбинаторной оптимизации NP, таких как проблема загрузки грузового контейнера, проблема загрузки грузового судна и т. д., поскольку проблема возникла из того, как выбрать наиболее подходящий элемент. Он назван в честь упаковки в рюкзаке. Эта проблема подразумевает условие, при котором существует только один элемент на элемент, что означает, что каждый элемент может быть выбран только из 0 или 1, поэтому это также называется проблемой рюкзака 0-1.

Стратегия разрешения

В этой задаче есть три распространенных жадных стратегии. Первый — выбрать в соответствии с весом предмета и каждый раз выбирать предмет с наименьшим весом. Второй — выбирать в соответствии со значением элемента каждый раз, когда выбирается элемент с наибольшим значением. Третий — определение концепции плотности значений. Каждый раз, когда выбирается элемент с самым легким весом, значение плотности s_iОпределяется как p_i/w_i。
В этом файле сценария Python автор инкапсулирует все три стратегии в функции. После получения соответствующих результатов сравните полученное общее значение и, наконец, выведите наиболее ценный результат.

Реализация алгоритма

Автор использует несколько инкапсулированных функций для получения результатов после их вызова в основной программе.

Функция инициализации

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

def Initial(): '' 'Определите вес, стоимость и общий вес рюкзака' ' option = input('Использовать ли данные по умолчанию (Да / Нет):') if option == 'Y': weight = [35, 30, 60, 50, 40, 10, 25] price = [10, 40, 30, 50, 35, 40, 30] C = 150 else: weight = list(map(int, input("Пожалуйста, введите вес предмета через пробел:").split( ))) price = list(map(int, input("Введите соответствующее значение элемента, разделенное пробелами:").split( ))) C = int(input(«Пожалуйста, введите общий предел веса рюкзака:»)) item = list(zip(weight,price)) print('Вес, значение:' + item.__str__() + '\ nПредел общего веса:' + C.__str__()) return item, C 

Три стратегии

Три функции используются для реализации трех стратегий выбора.Конечным результатом, возвращаемым функцией, является значение индекса после сортировки элементов согласно соответствующему методу выбора для использования функцией алгоритма.

def Weight(item): '' 'Выберите предмет наименьшего веса' '' data = np.array(item) idex = np.lexsort([-1*data[:,1], data[:,0]]) return idex def Price(item): '' 'Выбери самый ценный предмет' '' data = np.array(item) idex = np.lexsort([data[:,0], -1*data[:,1]]) return idex def Density(item): '' 'Выберите элемент с наибольшей плотностью значений' '' number = len(item) data = np.array(item) data_list = [0] * number for i in range(number): data_list[i] = (data[i,1])/(data[i,0]) data_set = np.array(data_list) idex = np.argsort(-1*data_set) return idex 

как поживаешь

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

def GreedyAlgo(item, C, idex): '''как поживаешь''' number = len(item) status = [0] * number total_weight = 0 total_value = 0 for i in range(number): if item[idex[i],0]  C: total_weight += item[idex[i],0] total_value += item[idex[i],1] status[idex[i]] = 1 C -= item[idex[i],0] else: continue return total_weight, total_value, status 

Функция сравнения

Сравните размер общего значения в результатах после расчета с помощью трех стратегий и верните набор результатов с наибольшим значением.

def Compare(total_value1, total_value2, total_value3): '' 'Сравните три результата' '' values = zip(total_value1, total_value2, total_value3) data = np.array([total_value1[1], total_value2[1], total_value3[1]]) idex = np.argsort(data) value = list(zip(*values)) results = list(value[idex[2]]) return results 

Основная функция

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

def main(): '' 'основная структура' '' item0, C = Initial() item = np.array(item0) idex_weight = Weight(item) idex_price = Price(item) idex_Density = Density(item) results_weight = GreedyAlgo(item, C, idex_weight) print(results_weight) results_Price = GreedyAlgo(item, C, idex_price) print(results_Price) results_Density = GreedyAlgo(item, C, idex_Density) print(results_Density) results = Compare(results_weight, results_Price, results_Density) print(results) 

Файл сценария

В файле сценария python, помимо перечисленных выше функций, есть две строки кода для реализации операции.

бегать

Выше весь код написан, давайте посмотрим на результаты запуска файла скрипта в fish.

Как показано на рисунке, fish показывает два результата работы с набором данных по умолчанию и набором данных, введенным вручную.

Вывод

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

Благодарность

Я многому научился у сообщества в течение всего процесса благодаря большинству пользователей сети.
Основное справочное содержание:
[1] «Удовольствие от алгоритмов» — Ван Сяохуа
[2]https://blog.csdn.net/sunny1235435/article/details/95603969.

Интеллектуальная рекомендация

[Структура данных и алгоритм] Array Приложение 3: Сжатие разреженного матрицы (реализация Java)

Посмотрите прямо под код программы: Результатом заключается в следующем: Финансируется в: https://blog.51cto.com/xplaf/1976965.

springmvc

Что такое SpringMVC Легкий каркас, похожий на struts2 Используйте режим архитектуры mvc для разделения веб-слоя springmvc — это webmvc в весенней структуре Сопоставление запросов, используемое для упр.

GCC Learning (2) U-boot.lds

Проанализируйте файл uboot.lds 1 Использование output_format (по умолчанию, Big, Little), указание формата вывода, формат ELF, 32 -бит инструкции ARM, небольшой конец. 2 output_arch (ARM) Указанная ар.

Конфигурация переменной установки и среды JDK-9

JDK -9 выпущен в сентябре 2017 года, учитываяОфициальное утверждение сайтаOracle не будет опубликовать дальнейшие обновления Java SE 8 к своим сайтам скачивания для коммерческого использования после к.

Определение начального значения переменной modelica

Когда я впервые использую Modelic, я не знаю, как определить начальное значение переменной. Обычно система по умолчанию устанавливает начальное значение равным 0, в результате чего некоторые симуляции.

Источник