Acerca de las preguntas clásicas de PASCAL

Problema de la reina. En un tablero de ajedrez, coloca 8 reinas de manera que no puedan atacarse entre sí (no siempre que estén en línea recta, es decir, que solo haya una reina en cada columna horizontal, columna vertical y columna diagonal). Encuentra todos los diseños.

programa ocho;

var a:array [1..8] de entero

b,c,d:array [-7..16; ] de número entero;

t,i,j,k:integer;

impresión del procedimiento

comenzar

t:=t +1;

escribir(t,' ');

para k:=1 a 8 escriba(a[k],' '); >writeln;

fin;

procedimiento try(i:integer

var j:integer

comenzar

para j:=1 a 8 haz {Cada reina tiene 8 posiciones posibles}

si (b[j]=0) y (c[i+j]=0) y (d [i-j]=0) luego {determinar si la posición entra en conflicto}

comenzar

a[i]:=j {colocar la reina}

b; [j]:=1; {Declara ocupación de la fila J}

c[i+j]:=1; {Ocupa dos diagonales}

d[ i-j]:=1 ;

si i<8 entonces try(i+1) {8 reinas no están terminadas, coloque recursivamente la siguiente reina}

si no, {Completa la tarea e imprime los resultados. }

b[j]:=0; {Retroceder}

c[i+j]:=0

d[ i-j]:=0; ;

fin;

fin;

comenzar

para k:=-7 a 16 hacer {inicialización de datos}

comenzar

b[k]:=0

c[k]:=0

d[k ]:=0;

end;

try(1);{Lugar desde la 1.ª reina}

end

Este es el contenido de Shenzhen. Buscar

Información de búsqueda:

Algoritmo de búsqueda

El algoritmo de búsqueda utiliza el alto rendimiento de la computadora para agotar intencionalmente un problema. Un método para encontrar una solución. un problema analizando algunas o todas las situaciones posibles

. El proceso de búsqueda es en realidad un proceso de construcción de un árbol de soluciones basado en las condiciones iniciales y reglas de expansión y de búsqueda de nodos que cumplan con el estado objetivo.

Desde la perspectiva de su implementación final del algoritmo, todos los algoritmos de búsqueda se pueden dividir en dos partes: la estructura de control y el sistema de generación, y la optimización y suma de todos los algoritmos

Mejoras se logran principalmente modificando su estructura de control. Ahora analizamos principalmente su estructura de control, por lo que se realizan las siguientes convenciones para su sistema de producción

:

Función ExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;

significa que el estado de nodo dado Situación se expande usando la regla de expansión ExpendWayNo y se devuelve el estado expandido.

(El lenguaje de descripción del algoritmo utilizado en este artículo es similar a Pascal.

)

Parte 1 Algoritmo de búsqueda básico

1. Algoritmo de retroceso

El algoritmo de retroceso es el algoritmo más básico entre todos los algoritmos de búsqueda. Utiliza una La idea de. ​​"Date la vuelta si no puedes lograrlo" es su estructura de control.

Es equivalente a usar el método transversal de raíz para construir el árbol de soluciones, que se puede usar para encontrar la solución o todas soluciones y la solución óptima. El algoritmo específico se describe a continuación:

[Algoritmo no recursivo]

Nodo (tipo de nodo) = Registro

Situación:TSituación (estado actual del nodo);

Vía-NO:Entero (número de reglas de extensión que se han utilizado);

Fin

Lista (tabla retrospectiva): Matriz [1..Max (profundidad máxima)] del nodo;

pos (número de nodo de expansión actual): Entero;

Lista<-0;

pos<-1;

Lista[1].Situación<-Estado inicial;

Mientras (pos>0(hay un camino por recorrer)) y ([objetivo no alcanzado])

Comenzar

Si pos>=Max entonces (desbordamiento de datos, salta del programa principal);

List[pos].Way-NO:=List[pos].Way-No+ 1;

Si (List[pos].Way-NO<=TotalExpendMethod) entonces (si hay reglas de expansión no utilizadas)

Comenzar

Si (el se pueden usar las reglas de expansión actuales) y luego

Comenzar

(Expandir el nodo actual con la regla de camino)

Lista[pos+1].Situación:= ExpendNode(Lista[pos].Situación,

Lista[pos].Camino-NO);

Lista[pos+1].Camino-NO:=0;

pos:=pos+ 1;

Fin-Si;

Fin-Si

Else Begin

pos:= pos-1;

End-Else

End-While;

[Algoritmo recursivo]

Procedimiento BackTrack(Situación:TSituación; deepth:Integer);

Var I:Integer;

Comenzar

Si deepth>Max entonces (el espacio alcanza el límite, salta de este proceso) ;

Si Situación=Objetivo entonces (encontrar el objetivo);

Para I:=1 a TotalExpendMethod haga

Comenzar

Retroceder (ExpendNode(Situación,I),deepth+1);

End-For;

End;

Ejemplo: Hay un caballero en un punto determinado. en un tablero de ajedrez M * M, y es necesario encontrar un camino a partir de este punto Saltar a través de todos los puntos del tablero de ajedrez sin repetir la ruta.

Evaluación: El algoritmo de retroceso consume menos espacio cuando se usa junto con el método de ramificación y unión, es útil para resolver problemas que se encuentran más profundos en el árbol de soluciones.

Mejores resultados. . Sin embargo, se debe evitar su uso en problemas en los que el nodo sucesor pueda ser el mismo que el nodo predecesor para evitar la creación de un ciclo.

2. Búsqueda en profundidad y búsqueda en amplitud

La estructura de control y el sistema de generación de búsqueda en profundidad y búsqueda en amplitud son muy similares. La única diferencia radica en la selección de nodos de expansión. Dado que conserva

todos los nodos predecesores, algunos nodos duplicados se pueden eliminar al generar nodos sucesores, mejorando así la eficiencia de la búsqueda. Estos dos algoritmos expanden todos los nodos secundarios de un nodo cada vez. La diferencia es que la siguiente expansión de la búsqueda profunda es uno de los nodos secundarios expandidos esta vez.

La búsqueda amplia expande los nodos hermanos del. El nodo se expandió esta vez.

Para mejorar la eficiencia en implementaciones específicas, se adoptan diferentes estructuras de datos.

[Búsqueda amplia]

Nodo (tipo de nodo) = Registro

Situación:TSituación (estado actual del nodo);

Nivel:Entero (profundidad del nodo actual);

Último:Entero (nodo principal);

p>

Fin

Lista(tabla de nodos):Array[1..Max(número máximo de nodos)] de Nodo( tipo de nodo);

open(número total de nodos):Entero;

close(número de nodo a expandir):Entero;

New-S:TSituation;(nuevo nodo)

Lista<-0;

abierto<-1;

cerrar<-0;

Lista[1].Situación<- Estado inicial;

Lista[1].Nivel:=1;

Lista[ 1].Último:=0;

Mientras (cerrar

(abrir< Max(el espacio no está agotado)) y

(Nodo de destino no encontrado) hacen

Begin

close:=close+1;

Para I:=1 a TotalExpendMethod hacer (Expandir un nivel de nodos secundarios)

Comenzar

Nuevo-S:=ExpendNode(Lista[cerrar].Situación,I );

Si no (Nuevo-S en la lista), entonces

(El nodo expandido nunca ha aparecido)

Comenzar

abrir :=abrir+1;

Lista[abrir].Situación:=Nuevo-S;

Lista[abrir].Nivel:=Lista[cerrar].Nivel+1;

Lista[abierta].Último: =cerrar;

Fin-Si

Fin-Para;

Fin-Mientras;

[Búsqueda en profundidad]

Abrir:Array[1..Max] de Node (tabla de nodos a expandir)

Cerrar: Matriz[1..Max] de Nodo; (tabla de nodos extendida)

openL,closeL:Integer (longitud de la tabla)

Nuevo- S:Tsituación; (nuevo estado)

Abrir<-0;Cerrar<-0;

AbrirL<-1;CerrarL<- 0;

Abrir[1].Situación<- Estado inicial;

Abrir[1].Nivel<-1;

Abrir[1].Último <-

0;

Mientras (openL>0) y (closeL

Comienzan

cerrarL:=cerrarL+1;

Cerrar[cerrarL]:=Abrir[abrirL];

abrirL:=abrirL-1;

Para I:=1 a TotalExpendMethod, haga (expandir una capa de nodos secundarios)

Begin

New-S:=ExpendNode(Close[closeL].Situation,I);

Si no (Nuevo-S en la lista), entonces

(El nodo expandido nunca ha aparecido)

Comenzar

openL:=openL + 1;

Abrir[openL].Situación:=Nuevo-S;

Abrir[openL].Nivel:=Cerrar[closeL].Nivel+1;

Abrir[openL].Last:=closeL;

Fin-Si

Fin-Para;

Fin;

Ejemplo : Problema de laberinto, resolviendo el camino más corto y el camino transitable.

Evaluación: la búsqueda amplia es un mejor método para encontrar la solución óptima y se optimizará aún más más adelante. La búsqueda profunda se usa principalmente cuando solo es necesario resolver

y hay muchos nodos repetidos en el árbol de soluciones y la repetición es difícil de juzgar, pero a menudo se puede reemplazar con A* o algoritmos de retroceso.

Parte 2 Optimización del algoritmo de búsqueda

1. Búsqueda de amplitud bidireccional

Aunque la búsqueda de amplitud puede obtener la solución óptima, su consumo de espacio aumenta demasiado rápido. Sin embargo, si realiza una búsqueda amplia tanto desde direcciones positivas como negativas, lo ideal es que el volumen de búsqueda se pueda reducir a la mitad, aumentando así la velocidad de búsqueda.

Ejemplo: hay N piezas de ajedrez blancas y negras dispuestas en fila, y hay dos espacios consecutivos en dos posiciones cualesquiera en el medio. Cada espacio puede intercambiar posiciones con dos piezas en la secuencia

, y el orden de las dos piezas permanece sin cambios. Se requiere ingresar y salir de un estado inicial y un estado objetivo de longitud, y encontrar el número mínimo de

pasos de transformación.

Análisis del problema: esta pregunta requiere encontrar el número mínimo de pasos de conversión, pero si utiliza la búsqueda amplia directamente, es fácil provocar un desbordamiento de datos. Pero si la expansión se lleva a cabo en ambas direcciones desde el estado inicial

y el estado objetivo al mismo tiempo, si los dos árboles de soluciones se superponen por primera vez en un determinado nodo, entonces el nodo

está conectado a El camino formado por los dos caminos es la solución óptima.

Mejoras en el algoritmo de búsqueda de amplitud:

1. Agregue una tabla de nodos como tabla de expansión inversa.

2. En el cuerpo del bucle while, agregue el código de expansión inversa después del código de expansión directa. El proceso de expansión no puede compartir un bucle for con el proceso directo.

3. Después de expandir un nodo hacia adelante, es necesario verificar si hay un nodo superpuesto en la tabla inversa. Lo mismo se aplica a la expansión inversa

.

Mejoras en el algoritmo de búsqueda de amplitud bidireccional:

Modifique ligeramente la estructura de control y solo expanda el número menor de nodos en las direcciones hacia adelante y hacia atrás cada vez en el ciclo while. , de modo que la velocidad de desarrollo en ambos lados se mantenga en un cierto equilibrio, reduciendo así el número de nodos de expansión total y acelerando la búsqueda.

2. Ramificar y enlazar

Ramificar y enlazar es en realidad un prototipo del algoritmo A*. Proporciona un valor esperado para cada nodo expandido si este valor esperado es. no es bueno

Si los resultados de la búsqueda actual son buenos, este nodo (incluidos sus nodos secundarios) se eliminará del árbol de respuestas para acelerar la búsqueda

.

Ejemplo: comprando en una tienda, sea Ci el precio del I-ésimo producto. Sin embargo, la tienda ofrece un descuento, que es una combinación de un grupo de productos. Si compra este grupo de productos a la vez, podrá disfrutar de un precio más favorable. Ahora dada una lista de compras y una lista de descuentos que ofrece la tienda, pide aprovechar estos descuentos y pagar el mínimo.

Análisis del problema: obviamente, el orden en que se utilizan los descuentos no tiene nada que ver con el resultado final, por lo que primero puede ordenar todos los descuentos por tasa de descuento de mayor a menor, y luego

use el método de retroceso para controlar la estructura, busque cada descuento en orden descendente desde su número máximo posible de usos hasta cero, suponiendo que A es el precio del descuento después del descuento, C es la suma de los precios minoristas actuales de los bienes sin descuento , entonces su valor esperado es A+a*C, donde a es la tasa de descuento del siguiente descuento

. Si el descuento actual es el último, entonces a=1.

Mejoras en el algoritmo de retroceso:

1. Agregue una variable global BestAnswer para registrar la solución óptima actual.

2. Cada vez que se genera un nodo, se calcula su valor esperado y se compara con BestAnswer. Si no es bueno, se llama al proceso de retroceso.

3. Algoritmo A*

El algoritmo A* introduce una función de valoración más general f, que se define como f=g+h. Donde g es el costo para llegar al nodo actual y h representa la estimación del costo para llegar al nodo objetivo desde el nodo actual. Debe cumplir dos condiciones:

1. h debe ser menor o igual al costo mínimo real h* de llegar al nodo objetivo desde el nodo actual.

2. f debe seguir aumentando monótonamente.

La estructura de control del algoritmo A* es muy similar a la de la búsqueda de amplitud, excepto que cada vez que se expande, es el que tiene el valor f más pequeño entre los nodos que se van a expandir actualmente.

el nodo expandido Si duplica un nodo expandido, este nodo será eliminado. Si se repite con el nodo a expandir, si la función de valoración de este nodo

es menor, se utilizará para reemplazar el nodo original a expandir. El algoritmo específico se describe a continuación:

Ejemplo: a 3* Hay ocho números del 1 al 8 y un espacio en el tablero de ajedrez de 3. Ahora se dan un estado inicial y un estado objetivo, y debemos usar este espacio para alcanzar el estado objetivo en el número mínimo de pasos.

Análisis del problema: El valor esperado se define como h=|x-dx|+|y-dy|.

La función de valoración se define como f=g+h.

Nodo (tipo de nodo) = Registro

Situación:TSituación (estado actual del nodo);

g :Integer ;(costo para alcanzar el estado actual)

h:Integer;(coste estimado)

f:Real;(valor de la función de valoración)

Último :Entero ;(Nodo padre)

Fin

Lista (tabla de nodos): Array[1..Max(número máximo de nodos)] de Nodo (Tipo de nodo);

abrir (Número total de nodos):Entero;

cerrar (Número de nodo a expandir):Entero;

New-S:Tsituation ;(Nuevo nodo)

Lista<-0;

abierto<-1;

cerrar<-0 ;

Lista[1].Situación<- Estado inicial;

Mientras (cerrar

(abrir

(nodo de destino no encontrado) hacer

comenzar

Empezar

cerrar:=cerrar+1;

Para I:=cerrar+1 abrir hacer (buscar el nodo con el valor de función de valoración más pequeño)

Comenzar

si Lista.f

Comenzar

Intercambiar Lista y Lista[cerrar];

End-If ;

End-For;

End;

Para I:=1 a TotalExpendMethod haga (expandir una capa de nodos)

Comenzar

Nuevo-S:=ExpendNode(Lista[cerrar].Situación,I)

Si no (Nuevo-S en Lista[1 ..close]) luego

(El nodo expandido no duplica el nodo expandido)

Comenzar

Si no (Nuevo-S en la lista[close+ 1..open]) luego

(El nodo expandido no se superpone con el nodo a expandir)

Comenzar

open:=open+1;

Lista [abierta]. Situación:=Nueva-S;

Lista[abierta].Último:=cerrar;

Lista[abierta].g: =Lista[cerrar].g+ costo;

Lista[abierta].h:=GetH(Lista[abierta].Situación);

Lista[abierta].f:=Lista [open].h+List [open].g;

Fin-Si

Si no Comienza

Si List[close].g+cost+GetH(New-S)

(El valor de la función de valoración del nodo extendido es menor que el mismo nodo)

Comenzar

Lista[igual].Situación:= Nuevo-S;

Lista[igual].Último:=cerrar;

Lista[ mismo ].g:=Lista[cerrar].g+costo;

Lista[igual].h:=GetH(Lista[abierto].Situación);

Lista[igual] ] .f:=List[open].h+List[open].g;

Fin-Si;

Fin-Else;

Fin- If

End-For;

End-While;

Mejoras en el algoritmo A* - A* en etapas:

Cuándo Cuándo Se produce un desbordamiento de datos en el algoritmo A *, se eliminan varios nodos con valores de función de valoración más pequeños de los nodos que se van a expandir y luego se descartan los nodos restantes que se van a expandir, para que la búsqueda pueda continuar.

Parte 3 Combinación de búsqueda y programación dinámica

Ejemplo 1. Hay una pieza de ajedrez con los lados 1, 6, 2, 4, 3 y 5 enfrentados. Ahora se proporciona un tablero de ajedrez M*N. Las piezas de ajedrez están inicialmente en el punto (1,1) y se colocan en el estado dado, ahora se requiere tirar desde el punto (1,1). apunte a ((1,1) en el número mínimo de pasos M, N) puntos y mire 1 hacia arriba.

Análisis: esta pregunta tiende a agotarse con una búsqueda simple, especialmente cuando M y N son grandes. Entonces puedes considerar usar programación dinámica para resolver el problema. Para una pieza de ajedrez, sólo hay 24 estados en total. En el punto (1,1), rueda hacia la derecha hasta el punto (2,1) y rueda hacia arriba hasta el punto (1,2). Y

El estado de cualquier punto (I, J) se deriva del estado de los puntos (I-1, J) y (I, J-1). Entonces, si se estipula que la pieza de ajedrez solo puede rodar hacia arriba y hacia la derecha, puede usar programación dinámica para deducir todos los estados posibles que alcanzan el punto (M, N). Obviamente, el camino desde (1,

1) hasta (N, M) estos estados es óptimo. Si 1 de estos estados está hacia arriba, se ha encontrado la solución. De lo contrario,

puede iniciar una búsqueda de amplitud desde el punto (M, N), usar el grupo de estados del punto (M, N) como estado inicial y verificar el estado actual en cada paso de expansión

Si el grupo de estados obtenido tiene el mismo estado que el estado del grupo de estados que llega a la cuadrícula; de ser así, la optimización y amplitud de la programación dinámica.

La optimización de la búsqueda puede garantizar que la solución óptima Excelente.

Ejemplo 2. Dado un entero positivo n con elemento básico a, se requiere encontrar a^n mediante el número mínimo de multiplicaciones.

Análisis: Idea 1: Esta pregunta se parece mucho a una pregunta de programación dinámica, a^n=a^x1*a^x2. Después de garantizar la optimización de a^x1 y a^x2

, se debe garantizar la optimización de a^n. Sin embargo, después de un análisis cuidadoso, se puede encontrar que puede haber algunas repeticiones en el proceso de multiplicación de a^x1 y a^x2, por lo que las partes repetidas deben restarse al calcular a^n. Dado que el cálculo de las partes repetidas es más engorroso, se puede convertir en un conjunto de cálculos de expansión.

La descripción es la siguiente:

I:=n;(split a^n)

split[n]:=x1;(plan de descomposición)

Usado[ n]:=Verdadero;(Números que aparecen durante la multiplicación)

Repetir(Descomponer números continuamente)

Usado[I-split[I]]:=Verdadero; p>

Usado[split[I]]:=True;

Dec(I);

Mientras (I>1) y (no Usado[I] ) hacer dec(I);

Hasta I=1;

Para I:=n hasta 1 hacer (calcular el número total de multiplicaciones)

Si Usado[I] luego cuenta:=cuenta+1;

Resultado:=cuenta;(devuelve el número de multiplicaciones)

Idea 2: Al analizar el resultado de la idea 1, El patrón se puede encontrar:

a^19=a^1*a^18

a^18=a^2*a^16

a^ 16=a^8 *a^8

a^8=a^4*a^4

a^4=a^2*a^2

a^2 =a*a

Para un n, primero construya el 2^k más cercano y luego use el 2^I generado durante el proceso de construcción para descomponer binariamente n-2^k,

La solución se puede obtener. El cálculo de tiempos se describe de la siguiente manera:

count:=0;

Repetir

Si n mod 2 = 0 entonces count:=count+1< / p>

De lo contrario cuenta:=cuenta+2;

n:=n div 2;

Hasta n=1;

Resultado:= count ;

Reflexión: Observa los siguientes datos:

a^15 a^23 a^27

Costo:5 Costo:6 Costo:6

a^2=a^1*a^1 a^2=a^1*a^1 a^2=a^1*a^1

a^3=a ^1 *a^2 a^3=a^1*a^2 a^3=a^1*a^2

a^6=a^3*a^3 a^5= a^ 2*a^3 a^6=a^3*a^3

a^12=a^6*a^6 a^10=a^5*a^5 a^12 =a ^6*a^6

a^15=a^3*a^12 a^20=a^10*a^10 a^24=a^12*a^12

a^23=a^3*a^20 a^27=a^3*a^24

Estos datos no utilizan los dos métodos de descomposición, pero son mejores que el segundo. idea. La solución dada en . Sin embargo, después de la prueba real, todas las soluciones de las ideas 1 y 2

están en la misma situación, pero no se puede obtener la solución de los datos anteriores.

Después de un análisis completo de los datos de a^2-a^15, se encontró que para

a^n, existen múltiples métodos de descomposición que pueden obtener la solución óptima, pero en la primera idea, sólo el Un conjunto de métodos de descomposición. Por ejemplo, para a^6

, solo se retiene a^2*a^4, interrumpiendo así la ruta de a^3*a^3, de modo que no se puede obtener el costo correcto al usar el algoritmo de idea 1. valor, de

y se pierde la solución óptima. Por lo tanto, al calcular la repetición de a^n=a^x1*a^x2, se debe introducir un proceso de búsqueda. Por ejemplo: a^15=a^3*a^12,

a^12=a^6*a^6 y a^6=a^3*a^3. Si se usa a^6=a^2*a^4, se debe usar un paso más.

Link=^Node (use una estructura de lista vinculada para registrar todas las soluciones posibles)

Node=Record

dividir :Entero;

siguiente :Enlace;

Fin;

Solución:Array[1..1000 ] de Enlace; (para todas las soluciones posibles de a^n)

Costo :Array[1..1000] de Integer; (costo de la solución)

max :Integer; límite superior calculado)

Procedimiento GetSolution;

Var i,j:Integer;

min,c: Entero ;

recuento:Entero;

temp,tail:Enlace;

plan :Matriz[1..500] de Entero;

nUsed:Array[1..1000] of Boolean;

Procedimiento GetCost(From,Cost:Integer); (Buscar y calcular la solución óptima)

Var temp:Link); ;

a,b :Booleano;

i :Entero;

Comenzar

Si Costo>c entonces Salir (poda)

Si Desde=1 entonces (condición de terminación recursiva)

Comenzar

Si Costo

Salir ;

Fin;

temp:=Solución[De];

Mientras temp<>NIL hacer (asunto de búsqueda)

Comenzar

a:=nUsed[temp^.Split];

Si no es a entonces inc(coste);

nUsed[temp^.Split]:= True ;

b:=nUsed[From - temp^.Split];

Si no b entonces inc(coste);

nUsed[From-temp ^ .Split]:=True;

i:=From-1;

Mientras (i>1) y (no nUsed) hacen dec(i);

GetCost(i,Cost);

Si no es a, entonces dec(coste);

Si no es b, entonces dec(coste);

nUsed [ Desde-temp^.Split]:=b;

nUsado[temp^.Split]:=a;

temp:=temp^.next;

Fin;

Fin;

Comenzar

Para i:=2 a Max do (la programación dinámica calcula todas las soluciones)

Comience

recuento:=0;

min:=32767;

Para j:

=1 a i div 2 hacer (descomponer I en I-J y J)

Comenzar

c:=32767;

FillChar(nUsed,Sizeof(nUsed ) ,0);

nUsed[j]:=True;nUsed[i-j]:=True;

Si j=i-j entonces GetCost(i-j,1)

Else GetCost(i-j,2);

Si c

Comenzar

recuento:=1;

min :=c;

plan[count]:=j;

Fin

Si no, si c=min, entonces

Inicio

p>

inc(cuenta);

plan[cuenta]:=j;

Fin;

Fin;

new(solución); (Construir lista enlazada de soluciones)

solución^.split:=plan[1];

solución^.next:=NIL;

Costo:=min;

tail:=solución;

Para que j:=2 cuente, haga

Empezar

nuevo( temp);

temp^.split:=plan[j];

temp^.next:=NIL;

tail^.next:=temp ;

tail:=temp;

Fin;

Fin;

Fin;

Problema de mochila:

Un viajero tiene una mochila que puede contener hasta m kilogramos. Ahora hay n tipos de artículos y los pesos de cada artículo son W1, W2,...,Wn,

<. p>Cada Los valores de las piezas son C1, C2,...,Cn respectivamente Si el número de piezas de cada artículo es suficiente

Encuentra el valor total máximo que pueden obtener los viajeros.

El modelo matemático de este problema es el siguiente:

Supongamos que f(x) representa el valor máximo cuyo peso no supera x kilogramos,

entonces f (x)=max {f(x-i)+c[i]} Cuando x>=w[i] 1<=i<=n

El método recursivo se puede utilizar para resolver el problema. El programa es el siguiente:

programa knapsack04

const maxm=200;maxn=30

tipo ar=array[0..maxn] de entero;

var m,n, j,i,t:integer

c,w:ar

función f(x:integer):integer;

var i,t, m:integer

comenzar

si x=0 entonces f:=0

comenzar;

t:=-1;

for i:=1 to n

comenzar

if x>=w[i ] entonces m:=f(x-i)+c[i ];

si m>t entonces t:=m

fin; =t;

fin;

fin;

comenzar

readln(m,n); para i:= 1 an hacer

readln(w[i],c[i]

writeln(f(m)); end

Explicación: Cuando m es pequeño, la programación es muy simple, pero cuando m es grande, es fácil agotar el tiempo.

4.2 Método recursivo mejorado

La idea del método recursivo mejorado es intercambiar espacio por tiempo. Esto solo requiere guardar los valores de cada subfunción durante el cálculo de la función recursiva y abrir una matriz unidimensional

El programa es el siguiente:

programa mochila04

const maxm=2000;maxn=30

escriba ar=array[0..maxn] de entero;

var m,n,j ,i,t:integer

c,w:ar

;

p:array[0..maxm] de entero;

función f(x :integer):integer

var i,t,m:integer

p>

comenzar

si p[x]<>-1 entonces f:= p[x]

si no

comenzar

si x=0 entonces p[x]:=0 más

comenzar

comenzar

si x=0 entonces p[x]:= 0 else

comenzar

p>

t:=-1

para i:=1 hasta n hacer

comenzar

si x>=w[i] entonces m:=f(i-w[i])+c[i]

si m>t entonces t:=m;

fin;

p [x]:=t

fin

f:=p[x]; p>

fin;

fin;

comenzar

readln(m,n); hacer

readln(w[i], c[i]);

fillchar(p,sizeof(p)

),-1);

writeln(f(m));

end

{se puede hacer con DP}