Algoritmos voraces

Algoritmos Voraces

Realizar los siguientes ejercicios

1. ¿Cuál es la mínima cantidad de canastas necesarias para empaquetar los artículos con los siguientes pesos (0.3, 0.9, 0.7, 0.5, 0.6, 0.2, 0.6, 0.8, 0.4, 0.1)? de acuerdo al algoritmo voraz de empaquetado. Escribe tanto la cantidad de canastas como los pesos de los artículos que contiene cada una.

Canasta 1 [0.3, 0.7] = 1

Canasta 2 [0.9, 0.1] = 1

Canasta 3 [0.5, 0.2] = 0.7

Canasta 4 [0.6, 0.4] = 1

Canasta 5 [0.6] = 0.6

Canasta 6 [0.8] = 0.8

Solución óptima:

Canasta 1 [0.9, 0.1] = 1

Canasta 2 [0.8, 0.2] = 1

Canasta 3 [0.7, 0.3] = 1

Canasta 4 [0.6, 0.4] = 1

Canasta 5 [0.6] = 0.6

Canasta 6 [0.5] = 0.5

2. Encontrar el árbol de recubrimiento mínimo para el siguiente grafo. En caso de utilizar el algoritmo de Prim, considerar el nodo A como el inicial.[pic 1]

Algoritmo de Prim.

v-s = {B, C, D, E, F}

cp = [ ]

Actual = A

        cp = [{A, B, 2}, {A, E, 11}]

        Arista = {A, B, 2}

        v-s = {C, D, E, F}

        aem = [{A, B, 2}]

        Actual = B

        cp = [{B, F, 10}, {B, C, 11}, {A, E, 11}]

        Arista = {B, F, 10}

        v-s = {C, D, E}

        aem = [{A, B, 2}, {B, F, 10}]

        Actual = F

        cp = [{F, D, 4}, {F, C, 7}, {F, E, 10}, {B, C, 11}, {A, E, 11}]

        Arista = {F, D, 4}

        v-s = {C, E}

        aem = [{A, B, 2}, {B, F, 10}, {F, D, 4}]

        Actual = D

        cp = [{D, C, 1}, {D, E, 6}, {F, C, 7}, {F, E, 10}, {B, C, 11}, {A, E, 11}]

        Arista = {D, C, 1}

        v-s = {E}

        aem = [{A, B, 2}, {B, F, 10}, {F, D, 4}, {D, C, 1}]

        Actual = C

        cp = [{D, E, 6}, {F, C, 7}, {C, E, 9}, {F, E, 10}, {C, B, 11}, {B, C, 11}, {A, E, 11}]

        Arista = {D, E, 6}

        v-s = { }

        aem = [{A, B, 2}, {B, F, 10}, {F, D, 4}, {D, C, 1}, {D, E, 6}]

        Actual = E

[pic 2]

3. Dibuja el siguiente grafo: G = ({A, B, C, D, E, F}, {{A,B}, {A, C}, {B,C}, {B,E}, {B,F}, {C,E},

{C,F}, {D,B}, {E,A}, {E,D}, {F,A}, {F,E}}).

[pic 3]

...