* 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. Compruebe 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 comienza con una capacidad de 0 y se prueba primero con el elemento 1. Las capacidades de 0, 1 y 2 no se pueden colocar, así que configúrelo en 0, y si la capacidad de la mochila es 3, coloque 4 en ella. de esta manera, la capacidad de esta fila de mochilas es 4, 5 y 6... .... Cuando son 10, la mejor solución es poner 4. Si el artículo número 1 se coloca en la mochila, entonces mira 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 5. 7, obviamente es 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, empujelos 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 artículo 3 no fue seleccionado en este momento. Se seleccionaron los artículos 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*/ /*Actualizar c[ i][j] si es mayor que la última mejor opción seleccionada */ 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",knapsack(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"); }