Как я могу решить проблемы ранца с 3 переменными?

Question

Как лучше всего решать проблемы, связанные с рюкзаком, которые имеют 3 переменные, такие как: стоимость, вес и объем?(с максимально возможным значением, с максимальным пределом веса и объема)

Я пытался использовать определенный индекс, основанный на его значении / (вес * объем), но я считаю, что это не даст мнелучшее решение, поэтому я искал, и некоторые люди предлагают использовать динамическое программирование, но все темы, связанные с этим, имеют только 2 переменные (значение и вес), и я не знаю, как на это может повлиять наличие более 2 переменных.

Answer 1

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

Как напоминание, стандартное решение DP для задачи о ранце работает, упорядочивая элементы в некотором порядке, затем отвечая на все вопросы следующего вида:

Какое максимальное значение можно получить, используя первые элементы i, не превышая вес w?

Это превращается в2D-таблица с одной осью для количества рассматриваемых предметов и другой для различных возможных значений веса.Чтобы заполнить таблицу, вы заполняете 1D срез записей, где i = 0, устанавливая их в ноль (вы не можете получить никакого значения, если у вас нет элементов), затем заполняете 1D срез, где i = 1, рассматриваявключать или исключать первый элемент, срез, где i = 2, учитывая, включать или исключать второй элемент и т. д. Тогда время выполнения составляет O (nW), где n - количество элементов, а W - максимально допустимоевес, поскольку это размеры таблицы, и вы выполняете O (1) работу для каждой записи.

Если у вас теперь есть два ограничения (вес и объем), вы можете решить все проблемы следующей формы:

Какое максимальное значение можно получить, используя первые элементы i, не превышая вес w или объем v?

Это превращается в трехмерную таблицу с одной осью длясколько предметов рассматривается, другой для различных возможных значений веса и третий для возможных значений объема.Чтобы заполнить таблицу, вы заполняете 2D-срез записей, где i = 0, устанавливая их в ноль (вы не можете получить никакого значения, если у вас нет элементов), а затем заполняете 2D-срез, где i = 1, с учетомвключать или исключать первый элемент, срез, где i = 2, принимая во внимание, включать или исключать второй элемент и т. д. Время выполнения - O (nWV), где n - количество элементов, W - максимально допустимый вес, а V - максимально допустимое значение, поскольку это число записей в таблице, и для заполнения каждого из них требуется O (1).

Видите ли вы, как адаптировать это для большего числа ограничений?

Answer 2

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

Я использую V для ссылки на начальный доступный том и Ш до начального имеющегося веса.Кроме того, я использую том [] для обозначения массива, в котором хранятся тома, аналогично взвешивая [] массив для весов.

Итак, для алгоритма динамического программирования необходимы 3 параметра: (1) Какой элементВы в настоящее время изучаете (назовите это i ), (2) сколько у вас осталось объема (назовите его vLeft )и (3) сколько веса у вас осталось (назовите это wLeft ).

И для оптимизации этого вы можете использовать следующую рекурсию:

DP [i] [vLeft] [wLeft] = min (DP [i + 1] [vLeft - громкость [i]][wLeft - weight [i]], DP [i + 1] [vLeft] [wLeft])

Левый аргумент в функции min - это когда мы выбираем элемент, а правый - когда мы нет.Кроме того, вам нужны некоторые базовые условия, когда не осталось ни объема, ни веса, и когда я достигну последнего элемента.

Но ваш начальный вызов будет примерно таким, где 0 - начальный индекс.

ComputeAnswer (0, V, W)