#python #dynamic #dynamic-programming #knapsack-problem
#python #динамический #динамическое программирование #рюкзак-проблема
Вопрос:
Я изучаю основные принципы программирования, и я застрял на проблеме динамического программирования. Давайте рассмотрим печально известную проблему с рюкзаком:
Учитывая набор элементов, каждый из которых имеет вес и значение, определите количество каждого элемента для включения в коллекцию, чтобы общий вес был меньше или равен заданному пределу, а общее значение было как можно большим.
Давайте установим ограничение веса на 10 и дадим два списка: веса = [2,4,7] и значения = [8,4,9] (я только что их составил). Я могу написать код, чтобы дать максимальное значение с учетом ограничения — это не проблема. Но что, если я хочу знать, какие значения я на самом деле использовал? Не общее значение — отдельные значения. Таким образом, для этого примера максимальными будут объекты с весами 2 и 7, для общего значения 8 9 = 17. Я не хочу, чтобы мой ответ читался как «17», хотя — мне нужен вывод списка, например: (8, 9). Это может быть легко для этой проблемы, но проблема, над которой я работаю, использует списки, которые намного больше и имеют повторяющиеся номера (например, несколько объектов имеют значение 8).
Дайте мне знать, если кто-нибудь может что-нибудь придумать. Как всегда, большая любовь и признательность сообществу.
Комментарии:
1. » печально известная проблема с рюкзаком»?
Ответ №1:
Считайте каждое частичное решение узлом. Просто добавьте все, что вы используете, в каждый из этих узлов, и какой бы узел ни стал ответом в конце, он будет содержать набор элементов, которые вы использовали.
Поэтому каждый раз, когда вы находите новое решение, вы просто устанавливаете список элементов в список элементов нового оптимального решения и повторяете для каждого.
Ответ №2:
Базовая реализация массива может помочь вам отслеживать, какие элементы позволили новому состоянию DP получить его значение. Например, если ваш массив DP w[] равен, у вас может быть другой массив p[] . Каждый раз, когда генерируется состояние w[i] , вы устанавливаете p[i] элемент, который вы использовали для перехода к ‘w [i]’. Затем, чтобы вывести список элементов, используемых для w[n] , выводите p[n] , а затем переходите к индексу n-weightOf(p[n]) , пока не достигнете 0, чтобы вывести все элементы.