Задача о ранце методом динамического программирования

      Комментарии к записи Задача о ранце методом динамического программирования отключены

Главная Форумы Программирование Помощь с решением задач на Prolog Решение головоломок на Prolog Задача о ранце методом динамического программирования

В этой теме 2 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 10 мес. назад.

  • Автор
    Сообщения
  • #2263

    questioner
    Участник

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

  • #2264

    Пусть набор предметов Bag стоимости Cost веса Weight является решением задачи. Некоторый предмет Item стоимости ItemCost веса ItemWeight может:

    • входит в Bag, тогда множество Bag\{Item} (без выбранного предмета) имеет стоимость Cost-ItemCost и является решением задачи для меньшего числа предметов и рюкзака вместимости Weight-ItemWeight;
    • не входит в Bag, значит набор Bag является решением задачи с меньшим числом предметов.

    Такое поведение описывается в виде формулы:

  • #2266

    На основе формулы возможно построить таблицу, отложив по строкам предметы, а по столбцам — вес. В каждой клетке таблицы записывается значение цены рюкзака. Первая строка таблицы будет содержать нули, т.к. не соответствует никакому предмету, однако она необходима для расчета других строк по формуле. Аналогично, первый столбец, соответствует рюкзаку нулевой вместимости, поэтому содержит одни нули. Когда таблица будет построена, оптимальное решение будет находиться в правой нижней клетке, из которой, следуя по вертикали или горизонтали в направлении наибольшего значения, можно восстановить решение (набор предметов Bag).

    На рисунке [1] приведен пример построения таблицы для предметов стоимости Cost = [ 55, 80, 60, 45, 105, 50 ] и веса Weight = [ 3, 2, 4, 1, 3, 105 ].

    Литература:

    1. Дж. Макконелл Анализ алгоритмов. Активный обучающий подход. — 3-е дополненное издание. М: Техносфера, 2009. -416с.

Для ответа в этой теме необходимо авторизоваться.