La idea básica del algoritmo codicioso
1. Establezca un modelo matemático para describir el problema.
2. Divida los problemas resueltos en varios subproblemas.
3. Resuelva cada subproblema y obtenga la solución óptima local al subproblema.
4. Sintetizar la solución óptima local del subproblema en una solución a la solución original del problema.
El proceso de implementación de este algoritmo:
A partir de una determinada solución inicial al problema;
Mientras que puede avanzar hacia un objetivo general dado
Encuentre un elemento de solución de la solución factible;
Una solución factible al problema se compone de todos los elementos de solución.
Naturaleza selectiva codiciosa
La llamada naturaleza de selección codiciosa significa que la solución óptima general del problema que está buscando se puede lograr a través de una serie de opciones óptimas locales. problema actual sin considerarlo. Este es el primer elemento básico de la viabilidad de los algoritmos codiciosos.
Los algoritmos codiciosos toman iterativamente decisiones codiciosas, y cada vez que se toma una elección codiciosa, el problema que está buscando se reduce a un subproblema más pequeño.
Para un problema específico, para determinar si tiene una naturaleza de elección codiciosa, es necesario demostrar que la elección codiciosa realizada en cada paso finalmente conduce a la solución óptima general al problema.
2. Propiedades óptimas de la subestructura <Br /> Cuando la solución óptima de un problema contiene la solución óptima de su subproblema, se dice que este problema tiene las propiedades subestructurales óptimas. La naturaleza de la subestructura óptima del problema es una característica clave que puede resolverse mediante algoritmos codiciosos.
El proceso general de la codicia
La copia del código es la siguiente:
Codicioso (c) // c es el conjunto de entrada del problema, es decir, el conjunto de candidatos
{
S = {}; // El conjunto de solución inicial es un conjunto vacío
mientras que (no solución (s)) // set s no constituye una solución al problema
{
x = seleccionar (c);
Si es factible (s, x) // juzga si la solución después de agregar x al conjunto s es factible
S = S+{x};
C = c- {x};
}
regreso s;
Descripción del problema:
Actualmente, hay monedas con valores faciales de 2 Jiao 5 centavos, 1 Jiao 5 centavos, 5 centavos y 1 centavos.
Análisis de problemas:
Según el sentido común, cuando vamos a la tienda para comprar cosas y encontrar dinero, el jefe siempre nos da la denominación máxima primero. Si el jefe le pide puntajes o algunos centavos, definitivamente no lo hará. De hecho, este es un problema típico de elección codiciosa.
Diseño de algoritmo e implementación del problema :
Permítanme darle un ejemplo primero. ¿Lo busca así? Lo hagas, entonces el jefe solo puede darme que obtuve 3 25 puntos y me dieron 24 menos, así que tuve que darme 2 10 puntos y 4 1 puntos.
La copia del código es la siguiente:
// aritmética para encontrar el cambio
// Entrada: Array M, almacene el número de valores faciales dispuestos de secuencia grande a pequeña.
// Salida: numeros de matriz, compare el número de monedas con diferentes valores de denominación en la matriz M y busque un plan de dinero
Public static int [] zhaoqian (int m [], int n)
{
int k = m.length;
int [] num = new int [k];
para (int i = 0; i <k; i ++)
{
num <i> = n/m <i>;
n = n%m <i>;
}
num de devolución;
}
La copia del código es la siguiente:
clase pública Zhaoqian
{
Public static void main (String [] args)
{
int m [] = {25,10,5,1};
int n = 99;
int [] num = new int [m.length];
num = zhaoqian (m, n);
System.out.println (N+"Plan de búsqueda de dinero:");
para (int i = 0; i <m.length; i ++)
System.out.println (num <i>+"zip"+m <i>+"valor nominal");
}
Public static int [] zhaoqian (int m [], int n)
{
int k = m.length;
int [] num = new int [k];
para (int i = 0; i <k; i ++)
{
num <i> = n/m <i>;
n = n%m <i>;
}
num de devolución;
}
}
Lo anterior es todo el contenido de este artículo, espero que te pueda gustar.