Dynami c Программирование для решения проблемы ранца 0/1 и возврата дополнительных приемлемых результатов - PullRequest
Новая
       91

Dynami c Программирование для решения проблемы ранца 0/1 и возврата дополнительных приемлемых результатов

0 голосов
/ 22 марта 2020

Общая информация:

Что такое проблема ранца?

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

В частности, проблема с ранцем 0/1 не позволяет брать дроби предметов.

Вот пример решения этой проблемы с помощью Dynami c Программирование: https://youtu.be/cJ21moQpofY

Пример:

Из видео выше - у нас есть набор предметов:

  • Значения: 2, 2, 4, 5, 3
  • Вес: 3, 1, 3, 4, 2
  • Макс. Вес: 7

После решения наш стол будет выглядеть так:

enter image description here

Из этого мы можем сказать, что максимальное значение равно 10, и мы выбрали пункты 2, 4 и 5

Мой вопрос:

Используя PHP, я написал рекурсивную функцию, используя памятку, которая правильно решает проблему KS, возвращает оптимальное решение и возвращает элементы, выбранные в этом оптимальном решении. То есть программа создает приведенную выше таблицу, чтобы найти решение, а затем работает в обратном направлении, чтобы найти элементы. Можно ли также найти дополнительные решения из той же таблицы? Скажем, я хочу найти 3 лучших решения?

Что я пробовал:

  1. Сначала я попытался использовать массив в рекурсивной функции для отслеживания из выбора. Проблема: если вы сбросите массив в конце ветви, вы потеряете предыдущие варианты root. поскольку функция рекурсивная, она может вызываться где-то из середины ветви.
  2. Одна мысль состоит в том, чтобы отслеживать рекурсивную глубину путем добавления переменной глубины к вызову функции. Сложение и вычитание из него по мере необходимости. Таким образом, возможно, я мог бы построить 2d (или 3d?) Массив дерева, показывающий каждый пройденный путь. Это кажется довольно тяжелым в пространстве?
  3. Моя текущая цель состоит в том, чтобы я мог как-то использовать таблицу, которая у меня уже есть, как в примере, и работать в обратном направлении из этого набора данных, чтобы найти результаты, меньшие, чем оптимальные. По сути, из приведенного выше примера я бы начал со строки 6, строки 5 (9), чтобы посмотреть, что произойдет, если я уменьшу емкость? или строка 7, строка 4 (9), чтобы увидеть, что произойдет, если я потеряю предмет? затем сравните результаты. Будет ли это на самом деле работать?

Обновление: ОК, я попробовал программирование в варианте 3 там. Короткий ответ, это не работает. Если бы у нас была полная таблица, мы могли бы работать в обратном направлении, чтобы получить другие результаты, но код довольно уродливый, и я не уверен, что он действительно более эффективен, чем разрешение для меньших элементов / весов. Кроме того, таблица из таблицы memo (массива) не полная, что означает, что мы действительно можем вернуть некоторые альтернативы, но они не являются исчерпывающими. Наш массив в виде таблицы выглядит примерно так: enter image description here

Обновление: Ответ на самом деле заключается в том, что вам нужно перезапустить функцию с различными ограничениями веса / элемента. Если вы подумаете об этом, любое неоптимальное решение не будет использовать весь KS или выберет меньшее количество элементов, поэтому просто решите его, уменьшив переменные ограничения ($ n, $ c). Вы можете отслеживать результаты вызовов функций, пока не найдете N-й лучший результат. Если вы хотите, скажем, первые 3 результата, это не проблема, но это может стать слишком интенсивным, если вам нужно отслеживать каждый результат из большого набора данных.

Мой код

Это * Код 1074 *, который в настоящее время решает KS с помощью динамического программирования c, используя запоминание и возвращает элементы, но только с оптимального результата. Позже я правильно запишу его в класс. 

<code><?php
$value = array(2, 2, 4, 5, 3);
$weight = array(3, 1, 3, 4, 2);

$maxWeight = 7;
$maxItems = 5;

$seen = array(array()); //2D array for memoization
$picked = array();

//Put a dummy zero at the front to make things easier later.
array_unshift($value, 0);
array_unshift($weight, 0);

//Call our Knapsack Solver and return the sum value of optimal set
$KSResult = KSTest($maxItems, $maxWeight, $value, $weight);
$maxValue = $KSResult; //copy the result so we can recreate the table

//Recreate the decision table from our memo array to determine what items were picked
//Here I am building the table backwards because I know the optimal value will be at the end
for($i=$maxItems; $i > 0; $i--) {
        for($j=$maxWeight; $j > 0; $j--) {
            if($seen[$i][$j] != $seen[$i-1][$j]
                && $maxValue == $seen[$i][$j]) {
                array_push($picked, $i);
                $maxValue -= $value[$i];
                break;
            }
        }
}

//Print out picked items and max value
print("<pre>".print_r($picked,true)."
"); echo $ KSResult; // Рекурсивная формула для решения проблемы KS // $ n = количество проверяемых элементов // $ c = общая вместимость сумки function KSTest ($ n, $ c, & $ value, & $ weight) {global $ seen; if (isset ($ seen [$ n] [$ c])) {// Мы видели эту подзадачу до возврата $ seen [$ n] [$ c]; } if ($ n === 0 || $ c === 0) {// Больше нет элементов для проверки или больше нет емкости $ result = 0; } elseif ($ weight [$ n]> $ c) {// Этот элемент слишком тяжелый, проверьте следующий элемент без этого $ result = KSTest ($ n-1, $ c, $ value, $ weight ); } else {// Получите более высокий результат сохранения или не сохранения элемента $ tempVal1 = KSTest ($ n-1, $ c, $ value, $ weight); $ tempVal2 = $ value [$ n] + KSTest ($ n-1, $ c - $ weight [$ n], $ value, $ weight); if ($ tempVal2> = $ tempVal1) {$ result = $ tempVal2; // некоторые условия могут go здесь? в противном случае используйте max ()} else {$ result = $ tempVal1; }} // запоминаем результаты и возвращаем $ seen [$ n] [$ c] = $ result; вернуть $ результат; }?>
...