Práctica 3: Técnicas Algorítmicas (Algoritmos III)

Ejercicio 03.02:

a)
b)
c)
d)

Ejercicio 03.03:

a)
b)
c)

Ejercicio 03.04:

a)
b)

Ejercicio 03.05:

i)
ii)
iii)

Ejercicio 03.06:

a)
Tomamos monedas de 25,10,5,1
Sol. Optima V = (v1,v2,..,vn) / v1 >= v2 >= .. >= vn
Sol. Optima G = (g1,g2,..,gn) / g1 >= g2 >= .. >= gn

qvq Sol. del Goloso G = V
Puede Pasar (G inc V) o (V inc G)? NO (suma de G = suma de V)
Vj < Gj (sino el goloso lo hubiera elegido)
Gj > Vj >= Vj+1 >= ... >= Vm
Ex. j / Vj != Gj Vi = Gi i<j

Valores Posibles

Gj	25	25	25	10	10	5
Vj	10	5	1	5	1	1

1) Vj = 1 -> Vj+1 .. Vm
No puede ocurrir porque la suma tenia que ser la misma, tampoco puede haber un 10 o 5
2) Vj = 5
No puedo tener otro 5 (para eso pongo un 5), tampoco puede haber un 25 en Gj
3) Vj = 10
Tampoco, ya que 10,10,5 no seria optimo

Conclusion: V = G

b)

Ejercicio 03.07:

a)
b)
c)

Ejercicio 03.08:

a)
b)
c)

Ejercicio 03.09:

a)
b)

Ejercicio 03.13:

a)
b)

Ejercicio 03.15:

a)
b)

Ejercicio 03.17:

a)
b)
c)

Ejercicio 03.18:

a)
b)
c)