Algoritmo - Challenge 5

////////////////////////////
// ALGORITMO DEL PROGRAMA //
////////////////////////////

FUNCTION costesDe( <costes>, <decisones>, <nivelk> ){
    - Declarar una variable <i> de tipo numérico
    - Inicializar la variable <i> al valor "1"

    - Declarar una variable <costeAcumulado> de tipo numérico
    - Inicializar la variable <costeAcumulado> al valor "0"

    MIENTRAS( <i> no sea mayor que <nivelk> ){
        - Incrementar el valor de <costeAcumulado> en el producto de valor del elemento <i> de <costes> por el valor del elemento <i> de <decisiones>
        - Incrementar el valor de <i> en una unidad
    :fin-MIENTRAS

    RETORNA( costeAcumulado )

:fin-FUNCION

// ES LA MISMA, PERO POR SEGUIR EL ESQUEMA LAS MANTENGO SEPARADAS
FUNCTION beneficioDe( <beneficios>, <decisones>, <nivelk> ){
    - Declarar una variable <i> de tipo numérico
    - Inicializar la variable <i> al valor "1"

    - Declarar una variable <beneficioAcumulado> de tipo numérico
    - Inicializar la variable <beneficioAcumulado> al valor "0"

    MIENTRAS( <i> no sea mayor que <nivelk> ){
        - Incrementar el valor de <beneficioAcumulado> en el producto de valor del elemento <i> de <beneficios> por el valor del elemento <i> de <decisiones>
        - Incrementar el valor de <i> en una unidad
    :fin-MIENTRAS

    RETORNA( beneficioAcumulado )

:fin-FUNCION

FUNCION buscar_optima( <costes>, <beneficios>, <n>, <capacidad>, <nivelk>, <x>, <<mejor>> ):

    - Asignar al elemento <nivelk> de <decisiones> el valor "0" // se decide no meter a la vaca k-ésima
    MIENTRAS( el valor del elemento <nivelk> de <decisiones> no sea "2" ):
        SI( el valor retornado por <costesDe(<costes>, <x>, <k>)> es menor o igual que <capacidad> ):
            SI( <nivelk> es igual que <n> ):
                // SE TRATA DE UNA SECUENCIA DE DESIONES COMPLETA Y FACTIBLE
                // Mirar si el beneficio es mayor que el que se, y actualizarlo en ese caso
                - Declarar una variable <aux> de tipo numérico
                - Asignar a <aux> el valor retornado por <beneficioDe( <beneficios>, <x>, <k> )>
                SI( <aux> es mayor que <mejor> ):
                    - Asignar a <mejor> el valor de <aux>
                :fin-SI
            :SI-NO:
                // SE TRATA DE UNA SECUENCIA DE DECISIONES PARCIAL Y FACTIBLE
                // En este caso se sigue contruyendo una secuencia de decisiones completa
                - Incrementar el valor de <nivelk> en una unidad
                - Llamar a <buscar_optima(<costes>, <beneficios>, <n>, <p>, <nivelk>, <x>, <<mejor>> )>
            :fin-SI
        :SI-NO:
            // SECUENCIA DE DECISIONES NO FACTIBLE
            // En este caso se hace poda, que es simplemente continuar sin hacer nada
        fin-SI:

        - Incrementar el elemento <nivelk> de <decisiones> en una unidad // "1" es que se decide meter a la vaca k

    fin-MIENTRAS

fin-FUNCION

PROGRAMA:

    - Declarar una variable <i> de tipo numérico
    - Declarar una variable <tmp> de tipo numérico

    REPETIR mientras( queden líneas ):

        - Declarar una variable <numeroDec> de tipo numérico
        - Declarar una variable <capacidad> de tipo numérico

        - Declarar un contenedor <pesos> de tipo vector de elementos de tipo numérico
        - Declarar un contenedor <beneficios> de tipo vector de elementos de tipo numérico

        - Leer un número y asignarlo a <numeroDec>
        - Leer un número y asignarlo a <capacidad>

        // LEER LOS COSTES
        - Asignar a <i> el valor "0"
        MIENTRAS( el valor de <i> sea menor que el valor de <numeroDec> ):
            - Leer un número y asignarlo a <tmp>
            - Añadir por el final de <costes> el valor <tmp>
            - Incrementar el valor de <i> en una unidad
        :fin-MIENTRAS

        // LEER LOS BENEFICIOS
        - Asignar a <i> el valor "0"
        MIENTRAS( el valor de <i> sea menor que el valor de <numeroDec> ):
            - Leer un número y asignarlo a <tmp>
            - Añadir por el final de <beneficios> el valor <tmp>
            - Incrementar el valor de <i> en una unidad
        :fin-MIENTRAS

        - Declarar un contenedor <decisiones> de tipo vector de elementos de tipo numérico
        - Ajustar el tamaño de <decisiones> al valor de <numeroDec>

        // LLAMADA AL ALGORITMO DE BACKTRACKING
        - Llamar a la función <buscar_optima( <pesos>, <beneficios>, <n>, <p>, "1", <tupla>, <<tmp> )>

        // MOSTRAR EL RESULTADO
        - Mostrar el valor de <tmp>
    :fin-MIENTRAS
:fin-PROGRAMA