¿Qué es la programación dinámica? ¿Cómo utilizar la programación dinámica para resolver problemas prácticos?

Aplicación del algoritmo de programación dinámica

1. Concepto de programación dinámica

En los últimos años, ha habido cada vez más problemas de competencia relacionados con la programación dinámica. casi al menos Hay un problema que debe resolverse mediante programación dinámica. Pero la competencia requiere que cada vez más jugadores utilicen conocimientos de programación dinámica y ya no se limita a la simple recursividad y el modelado.

Para comprender el concepto de programación dinámica, primero debemos saber qué es un problema de toma de decisiones en varias etapas.

1. Problema de toma de decisiones en varias etapas

Si un proceso de actividad se puede dividir en varias etapas interrelacionadas, cada etapa requiere una decisión (medida) y una etapa posterior a la decisión. Cuando se determina, a menudo afectará la decisión de la siguiente etapa, determinando así completamente la ruta de actividad de un proceso, lo que se denomina problema de toma de decisiones de múltiples etapas.

Las decisiones en cada etapa constituyen una secuencia de decisiones, que se denomina estrategia. Cada etapa tiene varias decisiones para elegir, por lo que hay muchas estrategias a nuestra disposición. De acuerdo con una estrategia, se puede determinar el efecto de la actividad y este efecto se puede determinar por la cantidad. Diferentes estrategias tienen diferentes efectos. El problema de la toma de decisiones en múltiples etapas consiste en seleccionar una estrategia óptima entre estrategias alternativas para lograr el mejor efecto bajo estándares predeterminados.

2. Terminología en problemas de programación dinámica

Fase: Dividir un proceso de resolución de problemas determinado en varias etapas interrelacionadas para facilitar la resolución del problema. El número de etapas puede ser diferente para diferentes procesos. Las variables que describen una etapa se denominan variables de etapa. En la mayoría de los casos, la variable de etapa es discreta y está representada por k. Además, también hay casos en los que la variable de etapa es continua. Una variable de etapa es continua si un proceso puede tomar una decisión en cualquier momento, permitiendo un número infinito de decisiones entre dos momentos diferentes.

En el ejemplo anterior, la primera etapa es el punto A, la segunda etapa es del punto A al punto B, la tercera etapa es del punto B al punto C y la cuarta etapa es del punto C. al punto d.

Estado: El estado representa las condiciones naturales u objetivas que se enfrentan al inicio de cada etapa, las cuales no están sujetas a la voluntad subjetiva humana y también se denominan factores incontrolables. En el ejemplo anterior, el estado es la posición inicial de una determinada etapa. No es solo el punto inicial de un camino en esta etapa, sino también el punto final de una rama en la etapa anterior.

En el ejemplo anterior, el primer nivel tiene un estado que es A, mientras que el segundo nivel tiene dos estados B1 y B2, el tercer nivel tiene tres estados C1, C2 y C3, y el cuarto El nivel es el estado D.

El estado de un proceso generalmente se puede describir mediante un número o un conjunto de números, que se denominan variables de estado. En términos generales, el estado es discreto, pero a veces, por conveniencia, se lo trata como continuo. Por supuesto, en la vida real, todos los estados son discretos debido a restricciones en la forma de las variables, pero desde una perspectiva analítica, a veces resulta útil tratar los estados como continuos. Además, el estado puede tener múltiples componentes (caso multidimensional), por lo que se representa mediante un vector; además, las dimensiones del estado en cada etapa pueden ser diferentes;

Cuando el proceso se desarrolla de todas las formas posibles, las variables de estado de cada etapa del proceso tomarán valores dentro de un rango determinado. El conjunto de valores de una variable de estado se denomina conjunto de estados.

Sin efectos secundarios: Requerimos que el estado tenga las siguientes propiedades: si se da el estado de una determinada etapa, el desarrollo del proceso posterior a esta etapa no se verá afectado por los estados de las etapas anteriores. Cuando se determinan todas las etapas, se confirma todo el proceso. En otras palabras, cada implementación de un proceso puede representarse mediante una secuencia de estados. En el ejemplo anterior, el estado de cada etapa es el punto inicial de la línea. Si se determina el orden de estos puntos, entonces toda la línea queda completamente determinada. A partir de la línea después de una determinada etapa, dado el punto inicial del segmento, no se ve afectado por la línea anterior (punto de paso). Esta propiedad de estado significa que la historia de un proceso sólo puede afectar su desarrollo futuro a través del estado actual, lo que se denomina sin efectos secundarios.

Toma de decisiones: Dado el estado de una etapa, la elección (acción) que evoluciona de ese estado a la siguiente etapa se denomina toma de decisiones. En control óptimo, también se le llama control. En muchos problemas, una decisión se puede representar naturalmente como un número o un conjunto de números. Diferentes decisiones corresponden a diferentes valores. Las variables que describen decisiones se denominan variables de decisión. Debido a que el estado no satisface los efectos posteriores, solo es necesario considerar el estado actual al seleccionar decisiones en cada etapa, sin considerar la historia del proceso.

El rango de variables de decisión se denomina conjunto de decisión permitido.

Estrategia: Una serie de decisiones en cada etapa se denomina estrategia. Para cada proceso práctico de toma de decisiones de múltiples etapas, las estrategias disponibles tienen un cierto límite de rango, llamado conjunto de estrategias permitidas. La política que permite el mejor efecto en el conjunto de políticas se denomina política óptima.

Dado el valor de la variable de estado x(k) en la etapa K, si se determina la variable de decisión de esta etapa, la variable de estado x(k+1) de la etapa k+1 es completamente determinado, es decir, x El valor de (k+1) cambia con el valor de x(k) y la decisión u(k) de la etapa K. Esta es la ley de transición de estado de la etapa K a la etapa k+1, que se denomina ecuación de transición de estado.

Principio de optimización: Como estrategia óptima de todo el proceso, satisface que las subestrategias restantes deben constituir la "subestrategia óptima" en relación con el estado formado por la decisión anterior.

El principio de optimización es en realidad una subestrategia de la estrategia óptima para problemas de demanda, y también es óptima.

Ilustremos esto volviendo a analizar el ejemplo anterior: de A a D, ¿sabemos que el camino más corto es A? ¿B1? ¿C2? d. La selección de estos puntos constituye la estrategia óptima en este ejemplo. Según el principio de optimización, cada subestrategia de esta estrategia debería ser óptima: ¿A? ¿B1? ¿El camino más corto de C2 a C2 es B1? ¿C2? D también es el camino más corto de B1 a D... - Esto es cierto, por lo que creemos que este ejemplo cumple con los requisitos del principio de optimización.

[Editar este párrafo] Ejercicio de Programación Dinámica

USACO

2.2 Suma de Subconjunto

Las preguntas son las siguientes:

Para un conjunto de números enteros consecutivos del 1 al n, se puede dividir en dos subconjuntos, asegurando que la suma de los números en cada conjunto sea igual.

Por ejemplo, si N=3, {1, 2, 3} se puede dividir en dos subconjuntos y la suma de todos los números en cada subconjunto es igual:

{ 3 } y {1, 2}

Esta es la única distribución (las ubicaciones de los conjuntos de intercambio se consideran del mismo esquema de partición y, por lo tanto, no aumentan el número total de esquemas de partición).

Si N=7, el conjunto {1, 2, 3, 4, 5, 6, 7} tiene cuatro métodos de división, y la suma de los números de cada subconjunto de distribución es igual:

{1, 6, 7} y {2, 3, 4, 5} {Nota 1+6+7=2+3+4+5}

{2, 5, 7 } y {1, 3, 4, 6}

{3, 4, 7} y {1, 2, 5, 6}

{1, 2, 4, 7 } y {3, 5, 6}

Dado n, su programa debería generar el número total de esquemas de partición, o 0 si no existe tal esquema de partición. Los programas no pueden almacenar resultados y generarlos directamente.

Nombre del programa: subconjunto

Formato de entrada

El archivo de entrada tiene solo una línea y solo un número entero n.

Ejemplo de entrada (archivo subset.in)

Siete

Formato de salida

Muestre el número total de esquemas de partición, o genere si no existe 0.

Salida de muestra (archivo subset.out)

Cuatro

El programa de referencia es el siguiente (lenguaje C):

# include & ltfstream & gt

Usar espacio de nombres std

const unsigned int MAX _ SUM = 1024

int

unsigned long long; int dyn[MAX _ SUM];

ifstream fin(" subconjunto . in "

of stream fout(" subconjunto . out "); int main() {

fin & gt& gtn;

fin . close();

int s = n *(n+1); p>

Si (s % 4) {

fout & lt& lt0 & lt& ltendl

fout close();

Return;

p>

}

s/= 4;

int i, j

dyn[0]= 1;

for(I = 1;i<= n;i++)

for(j = s;j>= I;j-)

dyn[j ]+= dyn[j-I];

fout & lt& lt(dyn[s]/2)& lt;& ltendl

fout . p>Devuelve 0;

}

USACO 2.3

Prefijo más largo

Las preguntas son las siguientes:

En Biología, la estructura de algunos organismos se representa mediante una serie de letras mayúsculas que contienen sus elementos. Los biólogos están interesados ​​en dividir secuencias largas en secuencias más cortas llamadas secuencias básicas.

Si los elementos del conjunto p se pueden concatenar (se permiten repeticiones; concatenación, equivalente al operador "+" en Pascal) para formar una secuencia S, entonces pensamos que la secuencia S se puede descomponer en los elementos en p , no todos los elementos deben estar presentes. Por ejemplo, la secuencia ABABACABAAB se puede descomponer en elementos del siguiente conjunto:

{BBC, British Broadcasting Corporation, Canadian Broadcasting Corporation}

Los primeros k caracteres de la secuencia s son llamado s Para un prefijo de longitud k, diseñe un programa que ingrese un conjunto de elementos y una secuencia de letras mayúsculas y calcule la longitud del prefijo más largo de esta secuencia.

Nombre del programa: prefijo

Formato de entrada

El comienzo de los datos de entrada incluye un conjunto de 1...200 elementos (longitud 1...10 ), expresado como una cadena continua separada por espacios. Todas las letras están en mayúscula, los datos pueden estar en más de una línea.

El final de una colección de elementos está marcado por una línea que contiene sólo un "." Los elementos de la colección no se repiten. Seguido de una secuencia de letras mayúsculas S, con una longitud de 1...200.000, representadas por una o más líneas de cadena, cada línea no debe exceder los 76 caracteres. El carácter de nueva línea no forma parte de la secuencia s

Ejemplo de entrada (prefijo de archivo. in)

BBC

.

ABABACABAABC

Formato de salida

Solo una línea, genera un número entero, que indica la longitud del prefijo más largo que S se puede descomponer en elementos en p.

Salida de muestra (prefijo de archivo. out)

11

El programa de muestra es el siguiente:

# include & ltstdio.h & gt

/*Número máximo de primitivas*/

#Definición MAXP 200

/*Longitud máxima de primitivas*/

#Definición MAXL 10

char prim[MAXP+1][MAXL+1];/*Primitivo*/

int nump/*Número primitivo*/

int start[200001];/*¿Es este prefijo de la secuencia expresable? */

char data[200000];/*sequence*/

int ndata/*longitud de la secuencia*/

int main(int argc, char **argv)

{

ARCHIVO *fout, * fin

int best;

int lv, lv2, lv3< / p>

if ((fin = fopen("prim.in "," r ")== NULL)

{

perror("fopen fin");

Salir(1);

}

if ((fout = fopen("prim.out "," w")) == NULL)

{

error(" fopen fout ");

Salir(1);

}

/ * Leer primitivo*/

mientras (1)

{

fscanf (fin, " %s ", prim[nump]);

p>

if (prim[nump][0]!= '.')nump++;

else break

}

/* Leer en cadena, una línea a la vez*/

ndata = 0;

while (fscanf (fin, " %s ", data+ndata) == 1)

ndata+= strlen(datos+ndata);

inicio[0]= 1;

mejor = 0;

for(LV = 0; lv & ltndatalv++)

if (start[lv])

{ /*para cada prefijo expresable*/

mejor = lv/*us A ¡Se encontró un prefijo expresable más largo */

/*Para cada primitiva, determine la secuencia a partir de

esta posición coincide con ella*/

for(lv2 = 0; lv2 & ltnumplv2++)

{

for(lv3 = 0; LV+lv3 & lt;ndata &&prime[Nivel 2 ][Nivel 3]&

prim[lv2][lv3]= = datos[LV+lv3];lv3++)

If (!prim[lv2][ lv3]) /*¡Coincidente! */

start[LV+lv3]= 1; /*Entonces el prefijo extendido también es muy expresivo*/

}

}

/*Comprueba si toda la secuencia es expresable*/

if(start[ndata])best = ndata;

fprintf (fout, " %i\n ", mejor);

Retorno 0;

}

USACO 3.1

Inflación fraccionada

Las preguntas son los siguientes:

p>

Intentamos diseñar nuestros juegos para que la gente pueda sumar tantos puntos como sea posible y necesitamos tu ayuda.

Podemos elegir temas de competición entre varias categorías. Aquí, una "categoría" se refiere a una colección de preguntas de competencia que se pueden resolver en la misma cantidad de tiempo y obtener la misma puntuación.

Tu tarea es escribir un programa que le diga al personal de USACO cuántos problemas se deben seleccionar de cada categoría para que el tiempo total para resolver los problemas esté dentro del tiempo especificado en la competencia y la puntuación total sea máxima. .

La entrada incluye el tiempo del partido, m (1

Cada línea posterior incluirá dos números enteros que describen una "categoría":

El primer número entero representa la puntuación (1

Tu programa debe determinar cuántos temas debemos elegir de cada "categoría" para obtener la puntuación más alta dentro del tiempo de juego.

De cualquier "categoría" "El número de preguntas puede ser cualquier número no negativo (0 o más).

Calcule la puntuación más alta posible.

Nombre del programa: dilatación

Entrada formato

Línea 65438+0: m, n tiempo de juego y número de "tipos" de preguntas

Línea 2-N+1: dos números enteros: cada pregunta de "categoría" <. /p>

Ejemplo de entrada (archivo inflate.in)

300 4

100 60

250 ​​​​120

120 100

35 20

Formato de salida

Una sola línea que contiene la puntuación máxima que se puede obtener dentro del límite dado

Ejemplo salida (archivo inflate.out)

605

{Seleccione dos preguntas de la segunda "categoría" y tres de la cuarta pregunta de "categoría"}

El El programa de muestra es el siguiente:

# include & ltfstream.h & gt

ifstream fin(" inflate . in ");

of stream fout(" inflar ");

const short maxm = 10010;

long best[maxm], m, n;

Vacío

main()

{

Corto I, j, len, pts

fin & gt& gtm & gt& gtn ;

para (j = 0; j & lt= m; j++)

mejor[j]= 0;

for(I = 0; i & ltn; i++) {

fin & gt& gtpts & gt& gtlen

for(j = len; j & lt= m;j++)

if( mejor[j-len]+pts & gt;mejor[j])

mejor[j]= mejor[j-len]+pts;

}

fout<<best[m]<<endl //Debido a que los elementos de la matriz no se reducen, el último elemento es el más grande.

}

USACO 3.3

Un juego

El tema es el siguiente:

Hay dos -juego de personas de la siguiente manera: n (2

Escriba un programa que implemente la estrategia óptima. La estrategia óptima es la estrategia que le permite obtener la mayor puntuación total posible en la situación actual. Su programa siempre debe ser el segundo El jugador ejecuta la estrategia óptima

Nombre del programa: juego1

Formato de entrada

La primera línea: entero positivo n, que indica el número de positivos. enteros en la secuencia <. /p>

La segunda línea al final: n enteros positivos (tamaño 1-200), separados por espacios

Entrada de muestra (archivo game1.in)

Seis.

4 7 2 9

5 2

Formato de salida

Solo hay una línea, dos números enteros. separados por espacios: en orden Las puntuaciones finales del Jugador 1 y del Jugador 2.

Salida de muestra (archivo game1.out)

18 11

El programa de referencia es el siguiente:

# include & ltstdio. h & gt

#Definir NMAX 101

int mejor[NMAX][2], t[NMAX]

int

Vacío

readx () {

int i, aux

freopen ("game1.in", "r", stdin);

scanf ("%d ",&n);

for(I = 1;i<=n;i++) {

scanf ("%d",& ampaux );

t = t[I-1]+aux;

}

fclose(stdin);

}< / p>

Int en línea

min (int x, int y) {

return x & gty? y:x;

}

Vacío

solve () {

int i, l;

for(l = 1; l & lt= n; l++)

for(I = 1; I+l & lt;= n+1; i++)

mejor[ l % 2]= t[I+l-1]-t[I-1]-min(mejor[I+1][(l-1)% 2),

mejor[(l - 1)% 2]);

}

void writex () {

freopen ("game1.out", "w", stdout <); /p>

printf ("%d %d\n ", mejor[1][n % 2], t[n]-mejor[1][n % 2]); fclose(stdout);

}

(Igual que Organizaciones internacionales) Organizaciones internacionales

main () {

readx();

solve();

writex();

Devuelve 0;

}

USACO 3.4

El músico de rock ruidoso

El título es el siguiente:

Acabas de obtener una N inédita (1

Es una Lástima que seas un fanático de la música clásica, no sabes cómo juzgar el mérito artístico de estas canciones, así que decides elegir según los siguientes criterios:

Las canciones deben aparecer en el CD. orden en que fueron escritas

Seleccione tantas canciones como sea posible

Nombre del programa: Rock Band

Formato de entrada

. Primera línea: tres números enteros: n, t, m