Esta es una pregunta DP / Bitmask bastante estándar. Primero, inventemos el conjunto de estados para nuestro DP. Llamemos a las diferentes posiciones en el campo p0, p1, …, p10. Almacenaremos la posición desde la que queremos comenzar a llenar jugadores y el conjunto de jugadores que queremos llenar en nuestro estado.
Un pequeño desvío para presentar lo que es una máscara de bits para principiantes. Una máscara de bits es solo un número entero ordinario. Podemos usar un número entero para almacenar cualquier subconjunto de un conjunto. Supongamos que un conjunto ‘S’ tiene 10 elementos, S = {e0, e1, …, e9}. Podemos asignar cada subconjunto de S a un entero único. ¿Cómo mapeamos un subconjunto a un entero? Asignemos el subconjunto A a un número entero n. Si el elemento [math] i ^ {th} [/ math] de S está presente en A, establezca el bit [math] i ^ {th} [/ math] (comenzando desde LSB) de n a 1, de lo contrario, configúrelo en cero.
Deje que nuestro estado dp [i] [j] denote la puntuación máxima que podemos lograr al llenar las posiciones pi a p10 usando solo los jugadores en el subconjunto denotado por j. Para generar el estado dp [i] [j], iteramos sobre todos los jugadores en j. Para cada jugador k en j, lo colocamos en la posición i. La puntuación máxima que podemos obtener colocando al jugador k en la posición i es igual a la calificación [k] [i] + dp [i + 1] [j ‘]. Aquí j ‘denota el número entero que representa el subconjunto representado por j menos el jugador k. Elegimos k tal que la calificación [k] [i] + dp [i + 1] [j ‘] sea máxima. dp [0] [x] (x: conjunto de todos los jugadores) contendrá la respuesta requerida porque representa la puntuación máxima posible para llenar las posiciones p0 a t10 usando todos los jugadores disponibles. Más formalmente:
- ¿Hay algún algoritmo que sea más rápido que log (n)?
- Algoritmos: ¿Cómo la combinación de ordenamiento tiene complejidad espacial O (n) para el peor de los casos?
- Sistemas distribuidos: ¿es posible utilizar el algoritmo de Paxos para generar números de secuencia (seqnums)?
- ¿Podemos construir un sistema utilizando algoritmos de aprendizaje automático que puedan reemplazar a todas las empresas de consultoría financiera y técnica del mundo?
- ¿Es CLRS realmente una 'introducción'? Si es así, ¿qué sigue?
dp [i] [j] = max {clasificación [k] [i] + dp [i + 1] [(j \ k)]
// j \ k denota la representación entera del conjunto representado por (j menos jugador k)
Enlace al código: Ideone.com
