Приёмная комиссия 2024

Полное руководство по решению задачи о рюкзаке с помощью динамического программирования

Полное руководство по решению задачи о рюкзаке с помощью динамического программирования
Содержание

Динамическое программирование (ДП) — это пошаговая стратегия решения задачи. На каждом следующем этапе используются результаты предыдущего. Начать изучение ДП можно с проблемы рюкзака. Исследуем условия задачи и алгоритм поиска ответа.

Подбери подходящий курс

Что такое задача о рюкзаке

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

Пример условия задачи

Вес и стоимость предметов:

1 $

8 $

18 $

22 $

28 $

1 кг

3 кг

5 кг

6 кг

7 кг

Вместимость рюкзака: 11 кг.

Проблема ранца (Knapsack Problem) — это задача на комбинаторную оптимизацию. Чтобы найти решение, нужно перебрать все возможные сочетания вещей при укладке рюкзака.

Как работает динамическое программирование

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

Как решить проблему рюкзака:

  1. Определить все комбинации грузов.
  2. Рассчитать стоимость каждого варианта.
  3. Сравнить варианты решения.
  4. Найти самое выгодное сочетание.

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

Источник: ru.freepik.com

Как решать задачу о рюкзаке

Правильная алгоритм решения задачи о рюкзаке основана на динамическом программировании. Стратегия решения универсальная. Чтобы записать алгоритм, можно использовать любой язык, с которым вы работаете. Для примера исследуем два варианта записи кода: на Python и на Java.

Алгоритм на Python

Пошаговая инструкция, как решить задачу о ранце:

  1. Создать таблицу dp размером (n + 1) x (W + 1). В этой таблице n — число предметов, а W — грузоподъемность рюкзака.
  2. Инициализировать первый столбец и первую строчку таблицы dp нулями.
  3. Проверить грузы i от 1 до n.
  4. Проверить общий вес w от 1 до W.
  5. Если вес груза i w, то dp[i][w] равно максимальному значению dp[i-1][w] и цене i плюс переменная dp[i-1][w-вес груза а i].
  6. Если условие выше не выполняется, dp[i][w] равно переменной dp[i-1][w].
  7. Подставляем итоговое значение в правый нижний угол таблицы dp как ответ.

Пример кода на Python:

import timeit

def knapsack (weights, values, capacity):

n = len (weights)

dp = )

else:

dp[i][w] = dp[i — 1][w]

return dp[n][capacity]



weights = [1, 3, 5, 6, 7]

values = [1, 8, 18, 22, 28]

capacity = 11

print (timeit.timeit ('knapsack (weights, values, capacity)', number=100, globals=globals ()))

>>> 0.007788784998410847

Пример использования алгоритма:

weights = [1, 3, 5, 6, 7]

values = [1, 8, 18, 22, 28]

capacity = 11

result = knapsack (weights, values, capacity)

print (result) # Вывод: 11

Алгоритм выбирает предметы весом 5 кг и 6 кг. Общая стоимость груза: 18 $ + 22 $ = 40 $.

Алгоритм на Java

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

  • n — общее количество предметов;
  • W — вместимость рюкзака.

Для решения создается таблица с размерностями 0—n и от 0—W. В нее сохраняются результаты выполнения подзадач, чтобы программа их не пересчитывала. Оптимальное решение находится на основе таблицы. В алгоритме используется восходящий подход к работе с данными.

Как записать алгоритм на Java:

int knapsackDP (int[] w, int[] v, int n, int W) {

if (n <= 0 || W <= 0) {

return 0;

}

int[][] m = new int[n + 1][W + 1];

for (int j = 0; j <= W; j++) {

m[0][j] = 0;

}

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= W; j++) {

if (w[i — 1] > j) {

m[i][j] = m[i — 1][j];

} else {

m[i][j] = Math. max (

m[i — 1][j],

m[i — 1][j — w[i — 1]] + v[i — 1]);

}

}

}

return m[n][W];

}

В коде присутствует вложенный цикл по номеру предмета n и вместимости рюкзака W. Время для обработки алгоритма — O (nW)

Ответ на задачу

Правильный ответ: в рюкзак нужно положить два предмета с ценой 18 $ и 22 $. Стоимость вещей, которые можно взять с собой, будет максимальной — 40 $. Выбранные предметы весят 5 кг и 6 кг, они помещаются в ранец на 11 кг. Грузоподъемность рюкзака используется на 100%.

Источник: ru.freepik.com

Типичные ошибки и как их избежать

Выбор самого дорогого предмета. Задача сформулирована так, что в ранце можно унести одну самую тяжелую и дорогую вещь. Но «очевидный» вариант всегда неправильный.

В примере можно подумать, что нужно взять предмет с весом 7 кг и ценой 28 $. Но лучше выбрать две другие вещи:

  • с весом 5 кг и ценой 18 $;
  • с весом 6 кг и ценой 22 $.

Стоимость груза: 40 $. Выбрав неправильный ответ, вы потеряете 12 $.

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

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

M (n, w) — это эффективное решение для n предметов с ограничением по вместимости рюкзака w.

Чтобы его найти, нужно выбрать максимальное из двух значений:

  • эффективное решение для (n-1) предметов при вместимости ранца w (предмет с номером n не учитывается при расчете);
  • стоимость n плюс оптимальное решение для (n-1) предметов при вместимости ранца w минус вес n.

Если вес n превышает грузоподъемность ранца, он исключается из возможных вариантов ответа. Эта ситуация относится к первому из описанных случаев.

Как записать решение методом рекурсии на Java:

int knapsackRec (int[] w, int[] v, int n, int W) {

if (n <= 0) {

return 0;

} else if (w[n — 1] > W) {

return knapsackRec (w, v, n — 1, W);

} else {

return Math. max (knapsackRec (w, v, n — 1, W), v[n — 1]

+ knapsackRec (w, v, n — 1, W — w[n — 1]));

}

}

На каждом этапе рекурсии оцениваются два из возможных решений. Время работы рекурсивного алгоритма — O (2 n).

Главное, что нужно знать

  • Динамическое программирование — это пошаговая стратегия решения задачи. На каждом следующем шаге используются данные из предыдущих этапов. Для решения составляется таблица, где сохраняются промежуточные результаты.
  • Задача о рюкзаке включает набор предметов и ранец с ограниченной грузоподъемностью. У каждого предмета есть стоимость и масса. Нужно определить, какие вещи взять с собой, чтобы получить максимальную прибыль после продажи.

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

alt

Всё для учебы доступно онлайн

Расписание, зачётку и домашние задания смотрите в приложении
Подберите программу обучения

ответьте на пять вопросов и узнайте, где будете учиться

Подобрать программу
Образование для карьеры
К каким профессиям вы более склонны?
Техническим Гуманитарным Творческим Медицинским
Какой у вас уровень образования?
Без образования Школа 9-11 класс Колледж Бакалавриат Магистратура Аспирантура
Какой формат обучения вам подходит?
Очно Заочно Онлайн По выходным дням
Интересует ли вас кредит на образование по ставке 3% в год?
Да Нет

Мы подобрали для вас программу обучения

Заполните форму, чтобы узнать больше о программе и наших предложениях

Подобрать программу и поступить

Политика конфиденциальности

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

Рамки Политики конфиденциальности

Настоящая Политика конфиденциальности (далее — «Политика») применяется к информации, полученной через данный сайт, иные сайты, виджеты и другие используемые интерактивные средства, на которых есть ссылка на данную Политику (далее — «Сайт») от пользователей Сайта (далее — «Пользователи»).

Нижеследующие правила описывают, как Университет «Синергия» обращается с любой информацией, относящейся к прямо или косвенно определенному или определяемому физическому лицу (субъекту персональных данных) (далее — «Персональные данные»), для целей оказания услуг с использованием Сайта.

Пользователи включают в себя всех физических лиц, которые подключаются к Сайту и используют Сайт.

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

Настоящая Политика конфиденциальности вступает в силу с момента ее размещения на Сайте, если иное не предусмотрено новой редакцией Политики конфиденциальности.

Контролирующие и обрабатывающие лица

Пользователи соглашаются с тем, что:

  • Пользуясь Сайтом, и принимая условия использования, опубликованные на Сайте, пользователь заявляет о своем однозначном согласии с обработкой его Персональных данных способами, описанными в настоящей Политике.
  • Обработка Персональных данных Пользователей осуществляется Оператором персональных данных — Университет «Синергия» (ИНН: 7729152149, ОГРН: 1037700232558).

С какой целью собираются эти данные

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

Сбор Персональных данных

При регистрации на Сайте Пользователи подтверждают свое согласие с условиями настоящей Политики и свое согласие на обработку своих Персональных данных в соответствии с условиями настоящей Политики, кроме того они соглашаются на обработку своих Персональных данных на серверах Университета «Синергия», расположенных на территории Российской Федерации.

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

  • «Как к Вам обращаться» в форме обратной связи, в случае если посетитель указывает свои полные ФИО или только часть;
  • Электронный адрес;
  • Номер телефона;
  • Также на сайте происходит сбор и обработка обезличенных данных о посетителях (в т. ч. файлов «cookie») с помощью сервисов интернет-статистики (Яндекс Метрика и других).
  • Вышеперечисленные данные далее по тексту Политики объединены общим понятием Персональные данные.

Как эти данные используются

На сайте используются куки (Cookies) и данные о посетителях сервисов (Яндекс Метрика и других). При помощи этих данных собирается информация о действиях посетителей на сайте с целью улучшения его содержания, улучшения функциональных возможностей сайта и, как следствие, создания качественного контента и сервисов для посетителей. Вы можете в любой момент изменить настройки своего браузера так, чтобы браузер блокировал все файлы cookie или оповещал об отправке этих файлов. Учтите при этом, что некоторые функции и сервисы не смогут работать должным образом.

Как эти данные защищаются

Для защиты Вашей личной информации мы используем разнообразные административные, управленческие и технические меры безопасности. Наша Компания придерживается различных международных стандартов контроля, направленных на операции с личной информацией, которые включают определенные меры контроля по защите информации, собранной в Интернет. Наших сотрудников обучают понимать и выполнять эти меры контроля, они ознакомлены с нашим Уведомлением о конфиденциальности, нормами и инструкциями. Тем не менее, несмотря на то, что мы стремимся обезопасить Вашу личную информацию, Вы тоже должны принимать меры, чтобы защитить ее. Мы настоятельно рекомендуем Вам принимать все возможные меры предосторожности во время пребывания в Интернете. Организованные нами услуги и веб-сайты предусматривают меры по защите от утечки, несанкционированного использования и изменения информации, которую мы контролируем. Несмотря на то, что мы делаем все возможное, чтобы обеспечить целостность и безопасность своей сети и систем, мы не можем гарантировать, что наши меры безопасности предотвратят незаконный доступ к этой информации хакеров сторонних организаций.

В случае изменения данной политики конфиденциальности вы сможете прочитать об этих изменениях на этой странице или, в особых случаях, получить уведомление на свой e-mail.

Политика в отношении обработки персональных данных.pdf

В случае изменения данной политики конфиденциальности вы сможете прочитать об этих изменениях на этой странице или, в особых случаях, получить уведомление на свой e-mail.

DMCA.com Protection Status