Aplicaciones de la programación dinámica
Memoria
Te regalo un triángulo digital, de la siguiente forma:
1
2 3
4 5 6
7 8 9 10
Encuentre una ruta desde la primera capa hasta la última capa para que la suma de los pesos pasados sea la más pequeña o la más grande.
Ya sea un novato o un experto experimentado, esta es una pregunta familiar. Podemos escribir fácilmente la ecuación de transición de estado:
f[i][j]=a[i][ j. ] + min{f[i+1][j], f[i+1][j+1]} (a[i][j] representa el estado actual, f[i][j] representa la función indicadora )
Para que el algoritmo de programación dinámica resuelva este problema, podemos escribir fácilmente el método de representación de bucle de programación dinámica basado en la ecuación de transición de estado y la dirección de transición de estado. Sin embargo, cuando los estados y las transiciones son muy complejos, puede que no sea tan sencillo escribir una programación dinámica cíclica.
Solución:
Intentamos analizar el problema desde una perspectiva positiva. Como en el ejemplo anterior, no es difícil encontrar una función recursiva muy simple: int?f. (int?i,?int ?j,?int?(*a)[4]){int?f1,?f2,?tmp=0,?k;if(i==0||j==0) return?a[0][ 0];if(j==i){for(k=0;k<=i;k++)tmp+=a[k][k];return?tmp;}f1=f( i-1,?j, ?a);f2=f(i-1,?j-1,?a);if(f1 Y la búsqueda de memoria ocupa relativamente poca memoria. Calcule el fragmento central: for(inti=n-1;i>=1;--i)//Comience desde la segunda hasta la última línea {for(intj=1;j<=i; j++) {if(a[i+1][j][1]>a[i+1][j+1][1])//El lado izquierdo es grande {a[i][j][2 ]=0;/ /Seleccione la izquierda a[i][j][1]+=a[i+1][j][1];}else//La derecha grande {a[i][j][ 2]=1;// Selecciona a[i][j][1]+=a[i+1][j+1][1];} a la derecha Ejercicios USACO2. 2 sumas de subconjuntos La pregunta es la siguiente: Para un conjunto de enteros continuos del 1 al N, se puede dividir en dos subconjuntos, y la suma de los números de cada uno Se garantiza que el conjunto será 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 uno de ellos es igual: { 3}y {1,2} Este es el único método de división (el intercambio de posiciones establecidas se considera el mismo esquema de división, por lo que no aumentará el número total de esquemas de división) Si N=7, hay cuatro formas de dividir el conjunto {1, 2, 3, 4, 5, 6, 7}, y la suma de los números en cada subconjunto distribuido 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. El programa no puede almacenar previamente los 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 ENTRADA DE MUESTRA (archivo subset .in) 7 FORMATO DE SALIDA Emite el número total de planes de partición, o 0 si no existe. SALIDA DE MUESTRA (archivo subset.out) 4 El programa de referencia es el siguiente (lenguaje C++): #include En biología, la estructura de algunos organismos está representada por una secuencia de letras mayúsculas que contienen sus elementos. Los biólogos están interesados en dividir secuencias largas en secuencias más cortas llamadas elementos. Si los elementos de un conjunto P pueden componerse de una secuencia S mediante una operación de unión (se permiten repeticiones; unión, es decir, ∪, es equivalente al operador "+" en Pascal), entonces Piensa que la secuencia S se puede descomponer es un elemento de P. No todos los elementos tienen que estar presentes. Por ejemplo, la secuencia ABABACABAAB se puede descomponer en los elementos del siguiente conjunto: {A, AB, BA, CA, BBC} Los primeros K caracteres de la secuencia S se llaman S Un prefijo de longitud K. Diseñar un programa que tome como entrada un conjunto de elementos y una secuencia de letras mayúsculas y calcule la longitud del prefijo más largo de la 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), Representado como una cadena consecutiva separada por espacios. Todas las letras están en mayúsculas y 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 "." No hay elementos duplicados en el conjunto. A esto le sigue una secuencia de letras mayúsculas S, con una longitud de 1 a 200.000, representadas por una o más líneas de cadena, cada una de las cuales no supera los 76 caracteres. El carácter de nueva línea no forma parte de la secuencia S. ENTRADA DE MUESTRA (prefijo de archivo. in) A AB BA CA 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 #define MAXP 200 #define MAXL 10 char prim[MAXP+1][MAXL+1]; int nump; int inicio[200001]; datos de caracteres[200000]; int ndata; int principal(int argc, char **argv) { ARCHIVO *fout, *fin; int best; int lv,lv2 , lv3; if ((fin = fopen(prim. in, r)) == NULL) { error (fopen fin); salir(1); } if((fout = fopen(prim.out, w)) == NULL) { error (fopen fout); salir(1); } mientras (1) { fscanf (fin, %s, prim[nump]); if (prim[nump][0] != '.') nump++; else romper; } ndata = 0; mientras ( fscanf (fin, %s, datos+ndata) == 1) ndata += strlen(datos+ndata); inicio[0] = 1; mejor = 0; for (lv = 0; lv < ndata; lv++) if (inicio[lv]) { mejor = lv; para (lv2 = 0; lv2 < nump; lv2++) { para (lv3 = 0; lv + lv3 < ndata && prim[lv2][lv3] == datos[lv+lv3++) if (!prim[lv2][lv3]) iniciar[ lv + lv3 ] = 1; } } si (inicio[ndata]) mejor = ndata; fprintf (fout, %i\n, best); return 0; } La programación dinámica es un algoritmo de competencia informática importante , tiene una gran flexibilidad. Los anteriores son algunos ejercicios introductorios. El aprendizaje profundo requiere una acumulación gradual de experiencia. Implementación del uso de programación dinámica (c++) al resolver el problema de la mochila 0-1 #include objeto de estructura typedef{ int peso; int valor; // tasa de flotación; } Objeto; Objeto * matriz ; //Matriz utilizada para almacenar información del objeto int num; //Número de objetos int container; //Capacidad de la mochila int **dynamic_table ; //Tabla de programación dinámica de almacenamiento bool * used_table; //Uso de almacenamiento de elementos //resulta la tabla de programación dinámica, es para detección void print_dynamic_table(){ printf (la tabla de programación dinámica es la siguiente:\n); /* for(int j=0; j<=container; j++) printf (%d ,j); printf(\n);*/ for(int i=1; i<=num; i++) { for(int j= 0 ; j<=contenedor; j++) printf(%d ,dynamic_table[i][j]); printf(\n); } } //Imprimir tabla de planificación dinámica void print_array(){ for(int i=1; i< = num; i++) printf(peso y peso del elemento %dth:%d %d\n,i,array[i].weight,array[i].value); } //Imprime los elementos de entrada //Clasificación por inserción, ordena de pequeño a grande según tasa=valor/peso//La programación dinámica considera todas las situaciones, por lo que no es necesario ordenar /*void sort_by_rate(){ for(int i=2; i<=num; i++) { Objeto temp=array[i]; for(int j=i-1; j>=1; j--) if(array[j].rate>temp.rate) array[j+1]=array[j]; else break; array[j+1]=temp; }}* / void print_used_object(){ printf(Los elementos utilizados son los siguientes:\n); for(int i=1; i< = num; i++) if(used_table[i]==1) printf(%d-%d\n, matriz[i].peso, matriz[i] . value); } //Imprimir el uso de los elementos /* Usado al realizar pruebas void print_used_table(bool * used_table ){ printf(tabla usada de la siguiente manera:\n); for(int i=1; i<=num; i++) p rintf(objeto %d es %d, i, used_table[i]); }*/ void init_problem(){ printf(mochila de entrada Capacidad:\n); scanf(%d, &container); printf(Ingrese el número de elementos:\n); scanf( % d, &num); array=new Object[num+1]; printf(ingrese el peso y el valor del artículo, formato como: 4-15\n) ; for(int i=1; i<=num; i++) { char c; scanf(%d%c%d, &array [i ].peso, &c, &array[i].value); // array[i].rate=array[i].value/array[i].weight; } print_array(); } //Revisar el uso de objetos void trace_back(){ int peso=contenedor; used_table=new bool[num+1]; for(int i=1; i<=num; i++) used_table [i]=0; //inicializa la tabla_usada para que no se use for(int j=1; j //Indica que se utiliza el elemento j if(dynamic_table[j][weight]!=dynamic_table[j+1][weight]) { weight-=array[ j].weight; used_table[j]=1; } // print_used_table(used_table); } //Comprueba si se utiliza el número número de elementos if(weight>=array[num].weight) used_table[num]=1;< / p> } voiddynamic_programming(){ dynamic_table=new int * [num+1]; for(int k=1; k<=num; k++) dynamic_table[k]=new int[container+1]; //dynamic_programming table //es bidimensional la tabla de programación dinámica asigna memoria for(int m=1; m for(int n=0; n<=container; n++) dynamic_table[m][n]=0; int temp_weight=array[num].weight; for(int i=0; i<=contenedor; i++ ) dynamic_table[num][i]=i //Inicializa la tabla de programación dinámica para(int j=núm -1; j>=1; j--) { temp_weight=array[j].peso; int temp_value=array[j].value; for(int k=0; k<=container; k++) if(k>=temp_weight && tabla_dinámica[j+1][k] < tabla_dinámica[j+1][k- temp_weight]+temp_value) dynamic_table[j][k]=dynamic_table[j+1][k-temp_weight]+temp_value; si no,dynamic_table[j][k]= dynamic_table[j+1][k]; }//Construir tabla de planificación dinámica print_dynamic_table();//Imprimir tabla de planificación dinámica } void main(){ init_problem(); dynamic_programming(); trace_back(); print_used_object(); }