Многократная проблема ранца ограничения

Question

Если существует более одного ограничения (например, и ограничение объема, и ограничение веса, когда объем и вес каждого элемента не связаны), мы получаем задачу о множественных ограничениях на рюкзак, проблему многомерных ранцев или m-мерная задача о ранце.

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

Проблема, с которой я сталкиваюсь, заключается в следующем

У меня есть функция ранца KnapSack (Capacity, Value, i) вместо общего KnapSack (Capacity, i), так как у меня есть верхние пределы для обоих. кто-нибудь может направить меня с этим? или предоставить подходящие ресурсы для решения этих проблем для достаточно большого n

или этот NP завершен?

Спасибо

Answer 1

Объединить ограничения. Посмотрите на http://www.diku.dk/~pisinger/95-1.pdf Глава 1.3.1 называется Объединение ограничений.

Например, скажем, у вас есть
переменная, ограничение1, ограничение2
1, 43, 66
2, 65, 54
3, 34, 49
4, 99, 32
5, 2, 88

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

Итак, у вас есть
переменная, объединенное ограничение
1, 430066
2, 650054
3, 340049
4, 990032
5, 20088

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

Answer 2

Хорошим примером послужит следующая задача:

Учитывая неориентированный граф G, имеющий положительные веса и N вершин.

Вы начинаете с суммы М денег. За прохождение через вершину i необходимо заплатить S [i] денег. Если вам не хватает денег - вы не можете пройти через эту вершину. Найти кратчайший путь от вершины 1 до вершины N, соблюдая вышеуказанные условия; или заявить, что такой путь не существует. Если существует несколько путей одинаковой длины, выведите самый дешевый. Ограничения: 1

псевдокод:

Set states(i,j) as unvisited for all (i,j)
Set Min[i][j] to Infinity for all (i,j)

Min[0][M]=0

While(TRUE)

Among all unvisited states(i,j) find the one for which Min[i][j]
is the smallest. Let this state found be (k,l).

If there wasn't found any state (k,l) for which Min[k][l] is
less than Infinity - exit While loop.

Mark state(k,l) as visited

For All Neighbors p of Vertex k.
   If (l-S[p]>=0 AND
    Min[p][l-S[p]]>Min[k][l]+Dist[k][p])
      Then Min[p][l-S[p]]=Min[k][l]+Dist[k][p]
   i.e.
If for state(i,j) there are enough money left for
going to vertex p (l-S[p] represents the money that
will remain after passing to vertex p), and the
shortest path found for state(p,l-S[p]) is bigger
than [the shortest path found for
state(k,l)] + [distance from vertex k to vertex p)],
then set the shortest path for state(i,j) to be equal
to this sum.
End For

End While

Find the smallest number among Min[N-1][j] (for all j, 0<=j<=M);
if there are more than one such states, then take the one with greater
j. If there are no states(N-1,j) with value less than Infinity - then
such a path doesn't exist.

Answer 3

Рюкзак с несколькими ограничениями - проблема упаковки. Прочитать. http://en.wikipedia.org/wiki/Packing_problem

Answer 4

Существуют жадные эвристики, которые рассчитывают «эффективность» для каждого элемента, которые работают быстро и дают приблизительные решения.

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

Существуют лучшие, более современные алгоритмы, которые труднее реализовать, см. Статьи Дж. Пучингера "Многомерная задача о ранце"!

Answer 5

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

knap[position][vol][t]

Теперь t=0, когда wt положительно, t=1, когда wt отрицательно.