Mochila cuantitativa PASCAL

Si K no se especifica,

f(m, volumen) = 0 cuando m=0

f(m, volumen) = f(m -1 , volumen) volumen-vol[m]lt; cuando 0

f(m, volumen)

= max { valor[m] f(m-1, volumen- vol[ m]), f(m-1, volumen) }

f(m, volumen) se refiere a lo que se puede lograr seleccionando elementos de los enumerados del 1 al m cuyo volumen total no exceda el volumen máximo. valor.

f(N, V) es lo que quieres.

Si se especifica K,

f(m, L, volumen)

= max { valor[m] f(m-1, L- 1 , volumen-vol[m]), f(m-1, L, volumen)}

f(m, L, volumen) = 0 l=0 o mlt cuando l

f(m, L, volumen) = f(m-1, L, volumen) volumen-vol[m]lt cuando 0

f(m, L, volumen) se refiere al esclavo; número El valor máximo que se puede lograr seleccionando L elementos cuyo volumen total no exceda el volumen de los elementos 1 a m.

f(N, K, V) es lo que quieres.

En cuanto a grabar los elementos seleccionados, puedes usar cadenas o matrices para registrarlos. Por ejemplo, N=8, ahora seleccione del 1 al 6. Si selecciona 6, el resultado de seleccionar del 1 al 5 es 00001010. Si no selecciona 6, el resultado de seleccionar del 1 al 5 es 00010011, luego busque en 00101010 (la sexta posición 1) Cualquiera que sea el valor que sea mayor que 00010011, la f solicitada y la cadena correspondiente se utilizarán como valor de retorno.

Hay muchos lugares donde se repiten los cálculos y se puede optimizar la poda, pero el programa será más complicado.

Suplemento:

El método que mencioné cuando no se especifica K es en realidad el método utilizado en el sexto piso. El volumen total extraído de los elementos numerados del 1 al i no excede t. Los elementos que maximizan el valor total se pueden dividir en dos situaciones. Una es no tomar el elemento n y seleccionar elementos con un volumen total que no exceda t de 1 a n-1 para maximizar el valor. y luego seleccione los elementos del 1 al n-1 para maximizar el valor total. Seleccione los elementos del 1 al i-1 cuyo volumen total no exceda t-tt[i] para maximizar el valor. El que tiene mayor valor total en estas dos situaciones es el que se busca.

Originalmente, esto se hace usando recursividad, y el método no recursivo requiere el uso de una pila. Sin embargo, si el volumen de cada elemento es un número entero positivo, se puede hacer usando el método recursivo. Este es el método utilizado en el sexto piso.

En el bucle doble, el bucle exterior es el elemento número 1 a N, y el bucle interior es el volumen V a 0, donde i=k. Después de un bucle, cada elemento b[j del. La matriz b[] ] almacena el valor máximo que se puede lograr seleccionando elementos de los elementos 1 a k para que la suma de los volúmenes sea exactamente j. Si a[j]=false, significa que la combinación de elementos no se puede seleccionar de modo que. que la suma de volúmenes es exactamente j. Esto cuando el correspondiente b[j]=0.

Por ejemplo, el volumen del elemento 5 es tt[5]=8, el valor es w[5]=13 e i=4. Al final del ciclo, b[8]=. 0, b[28]=46, b[29]=0, b[36]=55, luego i=5 después de que finaliza el ciclo, dado que a[0]=true, entonces a[0 tt[5]]. , es decir, a[8]=true, b[8] obviamente cambia del 0 original a 15, b[28] w[5]=59gt; b[28 tt[5]]=55, entonces b[36] ] se convierte en 59, y a[29]=false, b [29]=0, por lo que a[37] y b[37] permanecen sin cambios. Finalmente, una vez finalizado el ciclo i=N, lo que se busca es el más grande de b[1] a b[V]z.

Si el volumen no es un número entero y tiene una precisión de dos decimales, el volumen del artículo y el V especificado se pueden expandir 100 veces y convertir en un número entero para resolver el problema.

El elemento (j tt[i]lt;=t) en la declaración de juicio en el programa del sexto piso se puede eliminar, pero el rango de las matrices a[] y b[] debe ser restablecer, porque al final j tt[i] alcanzará el volumen total de todos los N elementos. Finalmente, el valor máximo todavía se obtiene de b[1] a b[V], y aquellos b[] que exceden V se ignoran.

El método del séptimo piso requiere que el valor p sea un entero positivo. El bucle externo sigue siendo el número de artículo y el bucle interno requiere el valor p de P a 0, donde P es el total. valor de todos los artículos.

La idea es la siguiente. De los elementos numerados del 1 al k, sacar los elementos con un valor total no menor que p para minimizar el volumen total. De la misma manera, tomar el elemento k y no tomar. el artículo k. Elija el de las dos situaciones.

La implementación del programa es similar a la del sexto piso, excepto que b[] se reemplaza por f[p], que representa el volumen mínimo que se puede lograr seleccionando elementos del 1 al k para que la suma de sus valores es exactamente p. Después de que finalice el último ciclo de la capa exterior k = N, busque aquellos f[p] más pequeños que V de f[1] a f[P], y el p más grande es lo que está buscando.

Cómo grabar: Se pueden utilizar matrices, estructuras y enumeraciones para grabar en C. Por ejemplo, para el método del sexto piso, agregue una M[V][N] para registrar el método. M[35][]={1, 0, 1, 0, 0,...0, 1, 0} significa tomar los elementos 1.º, 3.º y N-1. La suma de los volúmenes de estos tres elementos es. 35, en el ejemplo anterior, b[8] y b[36] cambian, por lo que M[8][] y M[36][] deben cambiar en consecuencia, es decir, M[8][5] y M[ 36][5] De 0 a 1, aquí 5 representa el quinto elemento, no el sexto elemento según la costumbre de C.

Si se especifica K, el método es en realidad el mismo y se analizará en dos situaciones. Lo primero que aprendí fue BASIC, luego C. Navegué brevemente en Pascal, pero nunca escribí un programa en Pascal. Ahora puedo leer pero no escribir. Tengo que explicar la idea general de la siguiente manera:

valor[1] a valor[N], vol[1] a vol[N] son ​​el valor y el volumen del artículo, V es el volumen de la mochila, y K es el número del artículo a llevar.

si L=0 o mlt; L entonces devuelve 0 y devuelve pickup=none //Si desea recoger 0 artículos o el número de artículos a recoger es mayor que el número de artículos restantes , por supuesto, solo puedes recoger nada

p>

si volumen-vol[m]lt;0 entonces f(m,L,volume) = f(m-1,L,volume ) devolver f y recoger // El volumen del artículo m es mayor que el espacio restante, solo considere Si no toma el artículo m, pero toma L artículos de 1 a m-1, la recolección permanece sin cambios

f(m, L, volumen) = max { valor[m] f(m-1, L-1, volumen-vol[m]), f(m-1, L, volumen)} //Si lo anterior Dos situaciones no son ciertas, entonces hay dos situaciones. Una es ir a m, de 1 a m. Tomar L-1 piezas de -1. Primero, no tome m, sino L piezas de 1 a m-1 <. /p>

retorno f y pastilla //Si f(m-1, L, volumen) es grande Entonces la pastilla es la pastilla devuelta por f(m-1, L, volumen), de lo contrario la pastilla es la pastilla devuelto por f(m-1, L-1, volumen-vol[m]). Modifíquelo y marque el elemento m como seleccionado.

f(N.K, V) es el valor máximo buscado, y la recogida devuelta es el método de adquisición.

El programa Pascal debe ser una función f(). El programa principal inicializa directamente el valor, vol, V, etc., y luego llama a f(N, K, V).

Dado que la función es recursiva, el espacio y el tiempo necesarios serán muy grandes cuando N aumente. Si usa un método no recursivo, será mejor. Puede usar el método de rama y enlace para podar. Por ejemplo, si no se selecciona 5, se calcula el resultado de seleccionar de 1 a 4, pero si se selecciona 5. seleccionado, 4 no está seleccionado, y ahora el resultado es de 1 a 3. Ganando, v no supera 6,4, y el cálculo anterior de 1 a 4 ya dio como resultado 1 a 3, v no supera 7,1 El valor de este. El resultado más 5 no es tan bueno como el cálculo anterior de 1 a 4, y mucho menos v no supera 6,4, por lo que no es necesario seguir calculando el resultado de 1 a 3, v no supera 6,4. Sin embargo, esto requerirá más variables para almacenar resultados intermedios, es decir, nodos intermedios en el árbol de búsqueda, y el programa también será complicado.

Todas las discusiones anteriores no consideraron la situación de soluciones múltiples. Si se toman 1, 2, 6 y 2, 4, el volumen total es 58, el valor total es 97 y es el óptimo. solución, entonces Todos los métodos anteriores solo pueden obtener un conjunto de soluciones. Si desea obtener todas las soluciones, debe cambiar la variable que guarda el método. M[1] a M[V] se pueden usar como punteros V a la lista vinculada. Si v=28 tiene tres conjuntos de soluciones, se pueden guardar con num[28]=3 o guardar en el nodo principal del vinculado. lista señalada por M[28]. No es necesario que el llamado a [m] anterior sea verdadero o falso, num [m] = 0 (en este momento M [m] apunta a nulo) o el nodo principal al que apunta M [m] es un solo nodo. De hecho, no es necesario registrar el número de soluciones. Cuando cambia la solución de v = 36, la lista vinculada de la solución de v = 28 se leerá naturalmente de principio a fin.