Mira el último ejemplo, el más complicado.
Tienes 8 grupos de dificultades (del 1 al 8) y en cada grupo tienes un número de opciones (2 para el nivel de dificultad 1, 1 para el nivel de dificultad 2, 2 para el nivel de dificultad 3...).
Evidentemente, tiene que elegir 5 problemas con 5 niveles de dificultad diferentes del conjunto de 8 niveles de dificultad diferentes. En su programa puede "recorrer" fácilmente todas las combinaciones posibles de dificultades:
$$ \\ 1 2 3 4 5\\ 1 2 3 4 6 \\ 1 2 3 4 7 \\ 1 2 3 4 8 \\ 1 3 4 5 6 \\ ...\\ 4 5 6 7 8 \\ $$
Mientras recorre la lista de combinaciones asocie "peso" a cada una de ellas. Fíjate en la primera, por ejemplo (12345): tienes 2 opciones para el nivel de dificultad 1, 2 opciones para el nivel de dificultad 3 y 3 opciones para el nivel de dificultad 5. El peso de la combinación 12345 es en realidad $2\times2\times3=12$ porque tiene 12 formas diferentes de seleccionar 5 problemas con dificultades 12345.
$$ \\ 1 2 3 4 5\implies weight=12\\ 1 2 3 4 6 \implies weight=4\\ 1 2 3 4 7 \implies weight=4\\ 1 2 3 4 8 \implies weight=4\\ 1 3 4 5 6 \implies weight=12\\ ...\\ 4 5 6 7 8 \implies weight=3\\ $$
Suma todos los pesos de todas las combinaciones de dificultades (12+4+4+4+12+...+3) y ya está.
EDIT: Otra solución.
La solución descrita anteriormente puede ser muy ineficiente. Si tienes un gran número de niveles de dificultad, recorrer todas las combinaciones y asignarles pesos puede ser muy lento. Hagámoslo utilizando la recurrencia.
Denota el número de problemas disponibles para un nivel de dificultad $i$ con $a_i$ . En su último ejemplo:
$$A=\{a_i|i=1,...,8\}=\{2, 1, 2, 1, 3, 1, 1, 1\}$$
Denote la longitud de la lista con $n$ (8 en el último ejemplo, el más complicado).
Denote el número de posibles selecciones de $k$ problemas con el menor nivel de dificultad igual a $i$ con $f(A, n, k, i)$ . Básicamente se quiere calcular $f(A, 8, 5, 1)$ .
Se tiene la siguiente fórmula de recurrencia:
$$f(A, n, k, i)=a_i\times f(A, n, k - 1, i + 1) + f(A, n, k, i + 1)\tag{1}$$
Esto significa básicamente que si necesita $k$ problemas que puedas:
- o bien empezar eligiendo uno de los problemas con nivel de dificultad $i$ ( $a_i$ diferentes formas de hacerlo) y combinarlos con $k-1$ problemas a partir del nivel de dificultad $i+1$
- o saltar el nivel de dificultad $i$ por completo y recoger todos $k$ problemas a partir del nivel de dificultad $i+1$ .
Siempre que se utiliza la recurrencia en programación, se necesita la condición de salida (la recurrencia tiene que parar en algún sitio). En este caso particular:
$$f(A, n, k, i)=0 \space \text{for}\space k\gt(n-i+1)\tag{2}$$
...lo que básicamente significa que no se puede seleccionar $k$ problemas con diferentes niveles de dificultad si su dificultad inicial (la más pequeña) $i$ es demasiado grande.
$$f(A, n, k, i)=1 \space \text{for}\space k=0\tag{3}$$
...lo que significa que sólo hay una forma de seleccionar "nada".
(1), (2) y (3) pueden traducirse fácilmente en un programa informático bastante eficaz:
public class Competition {
public static int f(int[] a, int k, int i) {
int n = a.length;
if(k > n - i) {
return 0;
}
if(k == 0) {
return 1;
}
return a[i] * f(a, k - 1, i + 1) + f(a, k, i + 1);
}
public static void main(String[] args) throws Exception {
int[] a = {2, 1, 2, 1, 3, 1, 1, 1};
System.out.println(f(a, 5, 0));
}
}
Tuve que hacer algunos pequeños ajustes en el código porque los índices están basados en cero en Java. El programa imprime 316 como se esperaba.
Un corto, ¿no? :)
