algorithm - volumen - problema de la mochila multiple eleccion

Problema de mochila de constricción múltiple

Question

Si hay más de una restricción (por ejemplo, un límite de volumen y un límite de peso, donde el volumen y el peso de cada elemento no están relacionados), obtenemos el problema de la mochila con restricciones múltiples, el problema de la mochila multidimensional o m problema de mochila tridimensional.

¿Cómo codigo esto de la manera más optimizada? Bueno, uno puede desarrollar una solución recursiva de fuerza bruta. Puede ser ramificado y encuadernado ... pero básicamente es exponencial la mayor parte del tiempo hasta que realice algún tipo de memorización o use programación dinámica que de nuevo requiere una gran cantidad de memoria si no se hace bien.

El problema que estoy enfrentando es esto

Tengo mi función KnapSack KnapSack (Capacidad, Valor, i) en lugar del KnapSack común (Capacidad, i) ya que tengo límites superiores en ambos. ¿Alguien puede guiarme con esto? o proporcionar recursos adecuados para resolver estos problemas para n razonablemente grande

o es este NP completo?

Gracias

Answer 1

Mochila con múltiples restricciones es un problema de embalaje. Leer. http://en.wikipedia.org/wiki/Packing_problem

Answer 2

Como un buen ejemplo serviría el siguiente problema:

Dado un gráfico no dirigido G que tiene pesos positivos y N vértices.

Empiezas con una suma de M dinero. Para pasar por un vértice i, debe pagar S [i] dinero. Si no tienes suficiente dinero, no puedes atravesar ese vértice. Encuentre la ruta más corta desde el vértice 1 hasta el vértice N, respetando las condiciones anteriores; o declarar que tal camino no existe. Si existe más de una ruta con la misma longitud, genere la más económica. Restricciones: 1

Pseudocódigo:

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

Fusiona las restricciones. Mire http://www.diku.dk/~pisinger/95-1.pdf capítulo 1.3.1 llamado Merging the Restraints.

Un ejemplo es decir que tienes
variable, constraint1, constraint2
1, 43, 66
2, 65, 54
3, 34, 49
4, 99, 32
5, 2, 88

Multiplica la primera restricción por un número grande y luego agrégala a la segunda restricción.

Así que tienes
restricción variable fusionada
1, 430066
2, 650054
3, 340049
4, 990032
5, 20088

A partir de ahí, haga cualquier algoritmo que quiera hacer con una restricción. El principal limitador que le viene a la mente es cuántos dígitos puede contener su variable.

Answer 4

Como dijiste que el volumen y el peso son cantidades positivas, trata de usar ese hecho de que el peso siempre disminuye:

knap[position][vol][t]

Ahora t=0 cuando wt es positivo, t=1 cuando wt es negativo.

Answer 5

Hay métodos heurísticos codiciosos que calculan una "eficiencia" para cada elemento, que se ejecutan rápidamente y proporcionan soluciones aproximadas.

Puede usar un algoritmo de bifurcación y enlace. Puede obtener un límite inferior inicial usando una heurística codiciosa, que se puede utilizar para inicializar la solución titular. Puede calcular los límites superiores para varios subproblemas considerando cada una de las limitaciones m una por vez (relajando las otras restricciones en el problema), luego use el límite más bajo como un límite superior para el problema original. Esta técnica se debe a Shih. Sin embargo, esta técnica probablemente no funcionará bien si ninguna restricción particular tiende a dominar la solución, o si la solución inicial de los codiciosos como la heurística no se acerca al óptimo.

Hay mejores algoritmos más modernos que son más difíciles de implementar. ¡Consulte los documentos de "problemas de mochila multidimensional" de J Puchinger!