algoritmo de programación dinámica para una variación de la mochila Problema

Question

Así que estaba pensando,

Yo quería hacer una variación sobre el problema de la mochila.

Imagine el problema original, con elementos con varios pesos/valor.

Mi versión tendrá, junto con los pesos/valores normales, un valor de "grupo".

por ejemplo. Elemento1 [5 kg, $ 600, electrónicas] ELEMENTO2 [1 kg, $ 50, los alimentos]

Ahora, tener un conjunto de este tipo de elementos, ¿cómo iba a codificar el problema de la mochila para asegurarse de que un máximo de 1 artículo de cada "grupo" está seleccionado.

Notas:

1. No es necesario para seleccionar un elemento de ese grupo
2. Hay varios elementos en cada grupo
3. usted todavía está minimizando el peso, maximizando el valor
4. El la cantidad de grupos está predefinida, junto con sus valores.

Estoy escribiendo un borrador del código en esta etapa, y he elegido utilizar un enfoque dinámico. Entiendo la idea detrás de la solución dinámica para el problema habitual de la mochila, ¿cómo modifico esta solución para incorporar estos "grupos"?

KnapSackVariation(v,w,g,n,W) 
{ 
    for (w = 0 to W) 
    V[0,w] = 0; 
    for(i = 1 to n) 
    for(w = 0 to W) 
     if(w[i] <= w) 
      V[i,w] = max{V[i-1, w], v[i] + V[i-1, w-w[i]]}; 
     else 
      V[i,w] = V[i-1, w]; 
    return V[n,W]; 
} 

Eso es lo que tengo hasta ahora, tengo que añadir que para que se retire todos los artículos correspondientes del grupo que está en cada vez que se soluciona esto.

Answer 1

Supongamos
c [I]: La categoría del i-ésimo elemento
V [i, w, S]: Valor máximo de la mochila de forma que contenga en el máximo un artículo de cada categoría en S

Recursive Formulation 
V[i,w,S] = max(V[i-1,w,S],V[i,w-w[i],S-{c[i]}] + v[i]) 
Base Case 
V[0,w,S] = -`infinity if w!=0 or S != {}` 

Answer 2

acaba de notar su pregunta tratando de encontrar una respuesta a una pregunta mía. El problema que ha mencionado es un problema bien conocido y bien estudiado llamado Problema de mochila de opción múltiple. Si busca en google encontrará todo tipo de información, y también puedo recomendar este libro: http://www.amazon.co.uk/Knapsack-Problems-Hans-Kellerer/dp/3642073115/ref=sr_1_1?ie=UTF8&qid=1318767496&sr=8-1, que dedica un capítulo entero al problema. En la formulación clásica de MCKP, debe elegir un elemento de cada grupo. Sin embargo, puede convertir fácilmente esa versión del problema a su versión agregando un ítem ficticio a cada grupo con ganancia y peso = 0, y los mismos algoritmos funcionarán. Le advierto que no intente adaptar el código del problema de la mochila binaria al MCKP con algunos ajustes: es probable que este enfoque lo conduzca a una solución cuyo rendimiento se reduce de manera inaceptable a medida que aumenta el número de elementos en cada grupo.