¿Cómo entender el problema de la mochila 0-1 en programación dinámica? Solicite ejemplos específicos y pasos detallados. . .

* Un viajero tiene una mochila que puede contener hasta M kilogramos. Ahora hay N artículos

Sus pesos son W1, W2,...,Wn,

Sus valores son P1, P2,...,Pn.

Si solo hay un artículo de cada tipo, el viajero podrá obtener el máximo valor total.

Formato de entrada:

M,N

W1,P1

W2,P2

... ...

Formato de salida:

X

*/

Porque se desconoce la capacidad máxima M de la mochila. Por lo tanto, nuestro programa debe probarse uno por uno desde 1 hasta M. Por ejemplo, comience seleccionando uno de N elementos. Vea si se puede colocar la mochila correspondiente a M. Si se puede colocar y aún hay más espacio, entonces el valor máximo de N-1 elementos se puede colocar en el espacio adicional. ¿Cómo podemos garantizar que la elección total sea el mayor valor? Vea la tabla a continuación.

Datos de prueba:

10,3

3,4

4,5

5,6

La matriz c[i][j] almacena el valor máximo de los elementos 1, 2 y 3 después de seleccionarlos en secuencia.

¿Cómo se obtiene este valor máximo de? la mochila Comenzando con una capacidad de 0, el artículo No. 1 se prueba primero. Las capacidades de 0, 1 y 2 no se pueden colocar. Por lo tanto, si la capacidad se establece en 0 y la capacidad de la mochila es 3, se colocarán 4. colocadas adentro, la capacidad de esta fila de mochilas es 4, 5 y 6.... Cuando son 10, la mejor solución es poner 4. Si se pone el artículo número 1 en la mochila, luego mire el artículo No. 2. Cuando la capacidad de la mochila es 3, la mejor solución sigue siendo la solución más barata en la fila anterior c es 4. Cuando la capacidad de la mochila es 5, la mejor solución es su propio peso de 5. Cuando. La capacidad de la mochila es 7, obviamente son 5 más un valor. ¿A quién agregar? Obviamente cuando 7-4=3 la mejor solución para c3 en la fila anterior es 4. Entonces. El mejor plan general es convertir 5+4 en 9. De esta manera, empuje hacia abajo fila por fila. Los datos colocados en el extremo derecho son los de mayor valor. (Tenga en cuenta que cuando la capacidad de la mochila en la fila 3 es 7, la mejor solución no es la 6 en sí, sino la 9 en la fila anterior. Esto significa que el elemento 3 no se seleccionó en este momento. Se seleccionaron los elementos 1 y 2. Entonces 9.)

Se puede ver en el proceso de construcción anterior el valor máximo.

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}Esto es lo que está escrito en el libro Ecuación de programación dinámica. ¿Está claro esta vez?

El siguiente es el programa real:

#include

int c[ 10][100 ];/*El valor máximo correspondiente a cada situación*/

int knapsack(int m,int n)

{

int i ,j,w [10],p[10];

for(i=1;i

scanf("\n%d,% d",&w [i],&p[i]);

for(i=0;i<10;i++)

for(j=0;j<100; j++)

c[i][j]=0;/*Inicializar matriz*/

for(i=1;i

for (j=1;j

{

if(w[i]<=j) /*Si la capacidad de la corriente El artículo es menor que la capacidad de la mochila*/

{

if(p[i]+c[i-1][j-w[i]]>c[i-1] [j])

/*Si el valor de este artículo más el valor de los artículos que se pueden colocar en el espacio restante de la mochila*/

/*Si es mayor que la última mejor opción seleccionada, actualice c[i][j] */

c[i][j]=p[i]+c[i-1][j-w[i]] ;

más

c[i][j]=c[i-1][j];

}

más c[i][j]=c[i-1][j ];

}

return(c[n][m]);

}

int main()

{

int m,n;int i,j;

scanf("%d ,%d",&m,&n);

printf("Ingrese cada uno:\n");

printf("%d",mochila(m,n)) ;

printf("\n"); /*La siguiente es una prueba de esta matriz, que se puede eliminar*/

for(i=0;i<10; i++)

for(j=0;j<15;j++)

{

printf("%d ",c[i][j] );

if(j==14)printf("\n ");

}

system("pausa");

}