(void *) blog

Posted on by fortytwo_de


En ocasiones, resolver un problema de forma directa, es ineficiente. Entonces, se resuelve un subproblema más sencillo. Al resolver el subproblema, podemos resolver el problema original. El caso más conocido en el que resolver un problema de forma directa es la sucesión de Fibonacci.

Esta sucesión, cada elemento está definido como la suma de los dos elementos anteriores. Formalmente:

$$ f(n) = f_{n-1} + f_{n-2} $$

Con los valores iniciales

$$ f(0) = 0, f(1) = 1 $$

Hasta aquí todo bien. Para calcular f(5), por ejemplo:

Problema: acabamos calculando el mismo número múltiples veces. Con números pequeños no es demasiado problema, pero esta función tiene complejidad exponencial, O(2^n); es decir, cada iteración del algoritmo tarda 2^n unidades de tiempo.

Afortunadamente, esto se puede arreglar. En resumen, el problema que causa la ineficiencia a la hora de calcular recursivamente el valor de la sucesión es el hecho de que se calcula muchas veces el mismo valor.

La solución

Está claro: guardar en algún tipo de memoria los valores que se calculan. En C++, por ejemplo, se puede usar el tipo vector<int>:

#include <iostream>
#include <vector>

using namespace std;

#define INFINITY -1

int fib(vector<int>& memory, int n) {
    if(memory[n] != INFINITY) return memory[n];
    int result = fib(memory, n-1) + fib(memory, n-2);
    memory[n] = result;

    return result;
}

int main() {
    int nth_elm = 10;
    vector<int> memory(nth_elm, INFINITY);
    memory[0] = 0;
    memory[1] = 1;      

    cout << fib(memory, nth_elm) << endl;
}

Card game

Una aplicación muy directa de la programación dinámica. Consiste en calcular el mínimo número de cartas (con unos valores constantes) con el que se puede obtener un valor concreto.

Este problema también es conocido como el problema de las monedas. El enunciado es el mismo, calcular el número mínimo necesario de monedas para alcanzar una cantidad concreta.

El enunciado del problema en la olimpiada infromática se puede descargar de aquí.

El enunciado establece los valores de las cartas:

Se puede obviar el palo de las cartas. Es decir, que tenemos cartas con valores {1, 5, 8, 14}. Para resolver este problema se tiene que definir una función que devuelva el mínimo número de cartas necesarias para alcanzar un número n.

No obstante, no se puede resolver el problema de forma directa: hay que dividirlo en subproblemas. Se puede definir el número mínimo de cartas para el número n como el número mínimo de cartas necesario para conseguir el número anterior + 1 carta.

Es decir:

$$ f(n) = f(n-i) + 1 $$

Con valores iniciales:

$$ f(0) = 0, f(1) = 1 $$

Siendo i el valor de una carta tal que el número de cartas para hallar n-i sea el menor de los cuatro posibles.

Por ejemplo, para hallar el número mínimo de cartas para obtener 2 se calcularía el mínimo número de cartas necesario para obtener 1 (n-i) y sumar 1. Es decir, para hallar el valor 2 se necesitan dos cartas.

Implementación

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define INFINITY -1

int find_min_cards(vector<int>& memory, int target) {
    if(target < 0) return INFINITY;
    int card_values[4] = {1, 5, 8, 14}, best = INFINITY;

    if(memory[target] != INFINITY) return memory[target];

    for(size_t i = 0; i < 4; i++) {
        int tmp = find_min_cards(memory, target - card_values[i]);
        if(tmp != INFINITY)
            if(best == INFINITY || tmp < best)
                best = tmp;
    } 
    // at this point, best = min_element(n-1, n-5, n-8, n-14)

    memory[target] = best+1;
    return best+1;
}

int main() {
    vector<int> values;
    int tmp;

    while((cin >> tmp) && tmp != -1) {
        values.push_back(tmp);
    }

    vector<int> memory(*max_element(values.begin(), values.end()) +1, INFINITY); // max value from the input vector

    memory[0] = 0;
    memory[1] = 1;

    for(size_t i = 0; i < values.size(); i++) {
        cout << find_min_cards(memory, values[i]) << endl;
    }

    return 0;
}

Nota: realmente el algoritmo puede funcionar sin los valores iniciales, pero es más "correcto" así.
Código disponible en hastebin.

Posted on by fortytwo_de | Posted in Algoritmos, C, Matemáticas, Programación


One Response to Programación dinámica

  1. oumaima mazouny says:


    thanks for sharing this formation
    you can see more formation here: here


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>