Selectividad Ciencias-Curso 2025-2026

A continuación aparecen los enunciados y las soluciones de los problemas de selectividad de la Comunidad Valenciana en formato .pdf, de junio y de julio para el bachillerato de ciencias sociales del curso 25/26.

Enunciados y soluciones de junio

Enunciados y soluciones de julio

El problema de la mochila (II)

Aplicamos un algoritmo genético para introducir en la mochila el mayor número de objetos que maximicen el beneficio pero sin superar la restricción de peso de la misma. En la tabla se muestra el problema a resolver: 4 objetos con diferentes utilidades y pesos.

La función objetivo Z no puede contener los 4 objetos pues rebasaría la restricción del peso que no puede superar el valor 15.

$$Z=4x_1+5x_2+6x_3+3x_4$$

$$P=7x_1+6x_2+8x_3+2x_4 \leq 15$$

Un cromosoma está formado por genes que son variables binarias. Cada cromosoma estará formado por una cadena de 4 bits. Si la suma de pesos de un cromosoma rebasa el peso máximo permitido 15, no se considera.

En la Tabla se muestran 4 cromosomas aleatorios de los cuales se tienen que obtener dos padres. La penúltima columna de probabilidad se obtiene dividiendo cada peso entre el total, y en la última columna la probabilidad acumulada.

• Selección:
Para obtener un padre debemos seleccionar uno de los 4 cromosomas. Se genera un número aleatorio (0.477) que supera a la probabilidad acumulada 0.2973; así el Padre 1 será el cromosoma 2: 1 0 1 0.
Se genera otro número aleatorio (0.934) que supera a la probabilidad acumulada 0.7027; así el Padre 2 será el cromosoma 4: 0 1 1 0.
.
• Cruzamiento:
Se asigna una probabilidad de cruzamiento entre dos genes de 0.98.  Se genera un número aleatorio 0.735<0.98 y entonces hay cruzamiento. Como hay 4 genes hay tres puntos de corte entre genes. Se genera otro número aleatorio (0.492). Como 1/3<0.492<2/3, el punto de corte está entre el gen 2 y el gen 3 (línea discontinua). Entonces se intercambian los genes 3 y 4.

• Mutación:
Se genera un número aleatorio para cada gen para ver si hay o no mutación. La habrá si es menor que el valor asignado 0.1. Los genes en rojo se han cambiado. Como el segundo cromosoma rebasa la restricción se elimina. Por tanto, hasta el momento, sólo hemos obtenido un hijo.

Repetimos el proceso, manteniendo la tabla inicial, para obtener nuevos hijos.

• Selección:
Para obtener un padre debemos seleccionar uno de los 4 cromosomas. Se genera un número aleatorio (0.802) que supera a la probabilidad acumulada 0.7027; así el Padre 1 será el cromosoma 4: 0 1 1 0.
Se genera otro número aleatorio (0.266) que no supera a la probabilidad acumulada 0.2973; así el Padre 2 será el cromosoma 1: 0 1 1 0.
.
• Cruzamiento:
Se asigna una probabilidad de cruzamiento entre dos genes de 0.98. Se genera un número aleatorio 0.174<0.98 y entonces hay cruzamiento. Como hay 4 genes hay tres puntos de corte entre genes. Se genera otro número aleatorio (0.740). Como 2/3<0.7401, el punto de corte está entre el gen 3 y el gen 4 (línea discontinua). Entonces se intercambia el gen 4.

• Mutación:
Se genera un número aleatorio para cada gen para ver si hay o no mutación. La habrá si es menor que el valor asignado 0.1. Los genes en rojo se han cambiado. Como el primer cromosoma rebasa la restricción se elimina. Por tanto sólo hemos obtenido un segundo hijo.

Volvemos a repetir el proceso para conseguir los dos hijos que faltan.

• Selección:
Para obtener un padre debemos seleccionar uno de los 4 cromosomas. Se genera un número aleatorio (0.658) que supera a la probabilidad acumulada 0.5676; así el Padre 1 será el cromosoma 3: 0 1 0 0.
Se genera otro número aleatorio (0.258) que no supera a la probabilidad acumulada 0.2973; así el Padre 2 será el cromosoma 1: 0 1 1 0.
.
• Cruzamiento:
Se asigna una probabilidad de cruzamiento entre dos genes de 0.98. Se genera un número aleatorio 0.989>0.98 y entonces no hay cruzamiento. 

• Mutación:
Se genera un número aleatorio para cada gen para ver si hay o no mutación. La habrá si es menor que el valor asignado 0.1. El gen en rojo se ha cambiado. Como los dos cromosoma cumplen la restricción se aceptan. Por tanto ya tenemos los 4 hijos.

Termina la primera iteración y vamos a iniciar la segunda iteración con estos 4 hijos. Para ello tomamos estos 4 hijos como cromosomas iniciales y construimos una nueva tabla.

Si suponemos que esta tabla es la obtenida después de varias iteraciones podemos considerar que representa los resultados finales donde los objetos a considerar para la mochila son el 2 y el 3 con una utilidad máxima de 11 y un peso de 14.

El problema de la mochila (I)

El problema de la mochila (knapsack problem) es el siguiente problema de optimización combinatoria:

  Dado un conjunto de elementos, cada uno con un peso y un valor, determinar qué elementos incluir en la colección para que el peso total sea menor o igual a un límite dado y el valor total sea el mayor posible.

El problema más sencillo (0-1 knapsack problem) es aquel en el que se restringe el número de copias de cada item a cero o uno.

Si n es el número de items numerados de 1 a n, cada uno con un peso wi y un valor vi, con una capacidad máxima de peso W, se trata de maximizar:

$$\sum_{i=1}^n v_ix_i$$

con la restricción:

$$\sum_{i=1}^n w_ix_i \leq W \hspace{0.2 cm} si \hspace{0.2 cm} x_i\in \{ 0,1 \}$$

El problema de la mochila acotada (BKP) elimina la restricción de que solo exista un ejemplar de cada artículo, pero restringe el número xi de copias de cada tipo de artículo a un valor entero máximo no negativo c. Por tanto la restricción es:

$$\sum_{i=1}^n w_ix_i \leq W \hspace{0.2 cm} si \hspace{0.2 cm} x_i\in \{ 0,1 \dots c\}$$

El problema de la mochila ilimitada (UKP) no impone un límite superior al número de copias de cada tipo de artículo y  la única restricción de xi es que sea un número entero no negativo:

$$\sum_{i=1}^n w_ix_i \leq W \hspace{0.2 cm} si \hspace{0.2 cm} x_i\in N$$

Vamos a resolver un ejemplo mediante programación dinámica:

Sean 5 objetos con los valores vi y pesos wi que se muestran en la Figura. Los pesos posibles en la mochila van desde 0 al máximo permitido de W=8 .

 Se establece una matriz M[i,j] donde cada elemento indica el beneficio máximo de llevar una mochila de peso j con objetos desde x1 hasta xi.

La primera fila de ceros corresponde  a no meter ningún objeto en la mochila y la primera columna de ceros indica mochila de tamaño cero que no admite ningún objeto.

Analicemos el funcionamiento observando las celdas coloreadas.  La matriz se va completando de izquierda a derecha y de arriba a abajo. Si estamos en la celda M[3,5]=7, retrocedemos 4 posiciones hasta la celda M[2,0]=0 ya que w3=4; ahora hacemos el cálculo siguiente:

$$M[3,1]+v_3=0+10=10>M[3,5]=7 \rightarrow M[4,5]=10$$

La celda M[5,5] también  vale 10 porque una mochila de peso máximo 4 no admite un objeto de peso 5.

La celda M[6,8] repite el valor 16 pues el valor que se obtiene (15) es menor que el de su celda superior.

El valor más alto de la última columna (19) indica el valor máximo.

Vamos a obtener los objetos con los que se consigue el valor máximo:

Al ser M[6,9]=M[5,9] el objeto W5=7 no se pone en la mochila. Como M[5,9]>M[4,9] el objeto w4=5 se pone en la mochila.

Retrocedemos 5 posiciones a  M[4,4] y siguiendo el mismo razonamiento no ponemos el objeto w3=4 y si ponemos el objeto w2=3. Continuando el proceso se llega a M[2,1]=0 y finaliza rl proceso.

Se han colocado en la mochila el objeto w2=3, v2=5 y el objeto w4=5, v4=14.

Problema del cambio de moneda (II)

Se trata de, dada una serie de monedas, devolver una cantidad determinada usando el menor número posible. Vamos a aplicar la Programación Dinámica para evitar los errores que se pueden producir utilizando un Algoritmo Voraz.

Existen n monedas diferentes y con una cantidad ilimitada de cada tipo: $$X_1 < X_2 < X_3 \cdots < X_n$$

Se trata de devolver una cantidad c, donde cambio(n,c) indica las mínimas monedas necesarias para devolver c usando X1, X2, X3,...Xn monedas.

• Si Xn>c no usamos esa moneda y cambio(n,c)=cambio(n-1,c).
• Si Xn<=c podemos usar esa moneda o no.
• Si usamos Xn entonces cambio(n,c-Xn)+1.
• Si no usamos Xn entonces cambio(n-1,c).
• De las dos opciones cogemos la menor cantidad.

Vamos a establecer una tabla con una matriz M((i,j)=cambio(i,j) donde i indica el número total de monedas <=Xi para devolver la cantidad j. Entonces cambio(i,j) es: $$cambio(i-1,j) \hspace{0.1 cm}si \hspace{0.1 cm} X_i>j$$ $$min(cambio(i-1,j),cambio(i,j-X_k)+1) \hspace{0.2 cm} si X_i\leq j$$

En la tabla la primera fila está numerada de 0 a c y la primera columna con los valores de las monedas incluida la posibilidad de no tener monedas. La primera columna de ceros indica que no se necesita ninguna moneda para devolver cero. La fila de infinitos indica que sin monedas no podemos devolver ninguna cantidad. La columna de infinitos indica que no podemos devolver 1 con monedas de valor superior. 

Vamos a explicar como se obtiene el elemento M(3,7) (verde) de la matriz. Para ello utilizamos los elementos M(2,7) M(3,4) (rojos) $$cambio(3-1,7)=M(2,7)=3 \hspace{0.2 cm} cambio(3,7-3)+1=M(3,4)+1=2$$ Al ser M(2,7)=3 se retroceden 3 posiciones desde la columna 7. De los dos valores obtenidos el menor es el que se asigna al elemento M(3,7). El razonamiento seguido, para todos los demás elementos de la matriz, es el mismo. El último elemento M(4,9) indica el número de monedas necesaria. 

  ¡Por tanto la solución óptima utiliza 3 monedas!

Vamos a ver el reparto de esas tres monedas. Para ello aplicamos el algoritmo siguiente: $$ si \hspace{0.2 cm} i>2 \land M(i,j)=M(i-1,j) \rightarrow i=i-1$$ $$ si \hspace{0.2 cm} no \rightarrow N(i)=N(i)+1 \land j=j-X_i$$

Empezamos en el último elemento M(4,8). Como M(4,8)=M(3,8)=3 subimos una fila y ahora M(3,8)=3<>M(2,8)=4 entonces el contador de monedas de valor 3 es N(3)=1 y retrocedemos 8-3 columnas y se repite el proceso a partir del elemento M(3,5) (verde) consiguiendo una segunda moneda de 3 y finalmente una moneda de 2.

¡Por tanto con 2 monedas de 3 y una de 2 se devuelve la cantidad 8 !

Problema del cambio de moneda (I)

Dado un monto M de monedas y un conjunto de denominaciones D (billetes o monedas) se busca la mínima cantidad de denominaciones cuya suma sea M.

No existen restricciones sobre el número de billetes o monedas de una denominación y sobre el uso repetido de billetes o monedas.

Vamos aplicar un algoritmo voraz: se elige la opción óptima en cada paso con la esperanza de llegar a una solución general óptima.

Sea un monto de M=36 monedas y denominaciones D={1,2,5,10,20}. Se elige en cada paso la mayor moneda posible y así sucesivamente:

• paso 1: 36-20=16
• paso 2: 16-10=6
• paso 3: 6-5=1
• paso 4: 1-1=0

Por tanto la solución general es: S={20,10,5,1} que suman 36. Además es óptima porque no existen otra solución con menos monedas. 

No siempre la suma de las soluciones óptimas de cada paso dan una solución óptima general. Si ahora las denominaciones son D={1,2,5,10,18,20} también se tiene:

• paso 1: 36-20=16
• paso 2: 16-10=6
• paso 3: 6-5=1
• paso 4: 1-1=0

Sin embargo la solución óptima es: S={18,18} que también suman 36. Aunque a veces puede no fallar, por ejemplo, si el monto es M=39:

• paso 1: 39-20=19
• paso 2: 19-18=1
• paso 3: 1-1=0

Por tanto la solución general es: S={20,18,1} que suman 39. 

Para que el algoritmo no falle nunca es necesario que cada clase de moneda sea igual o mayor que una sucesión de potencias. No puede haber dos clases de monedas que cumplan la misma condición. $$k^0,k^1,k^2,\cdots k^n$$ En nuestro ejemplo válido: $$2^0\leq1, 2^1\leq2,2^2\leq5,2^3\leq10,2^4\leq20$$ En las monedas del euro se cumple este criterio: $$2^0\leq1, 2^1\leq2,2^2\leq5,2^3\leq10,2^4\leq20,2^5\leq50,2^6\leq100$$ 

 Para que no falle nunca se utiliza la Programación Dinámica.