# TDA | Practica 1 Ejercicio 14 Suma Selectiva
**14.** Dado un conjunto $X$ con $|X| = n$ y un entero $k$ con $k \leq n$, queremos encontrar el máximo valor que pueden sumar los elementos de un subconjunto $S$ de $X$ de tamaño $k$. Más formalmente, queremos calcular
$$
\max_{S \subseteq X, |S|=k} \sum_{s \in S} s.
$$
a) Proponer un algoritmo *greedy* que resuelva el problema, demostrando su corrección. Extender el algoritmo para que también devuelva uno de los subconjuntos $S$ que maximiza la suma.
b) Dar una implementación del algoritmo de inciso a) con complejidad temporal $O(n \log n)$.
c) Dar una implementación del algoritmo de inciso a) con complejidad temporal $O(n \log k)$.
# Resolución
## a)
```python
def sumaSelectiva(X, k):
xSorted = sorted(X)
return sum(xSorted[-k:]), xSorted[-k:]
```
### Demostración de correctitud
#### Por el absurdo:
#
- Suponemos que hay un conjunto optimo $S^*$ de tamaño $k$ pero que **no incluye** a uno de los K más grandes.
- Sea $X \subseteq S^*$ el elemento que no está entre los $k$ elementos más grandes de $X$, tiene que existir un $x_t \subseteq X$ que $x_t \not \subset S^*$. Además: $x_t > x_i$ pues $x_t$ es de los $k$ más grandes.
- Si los swappeamos y llamamos a este nuevo conjunto $S'$ su suma sería mayor a la de $S^*$ y esto es absurdo, porquie dijimos que $S^*$ era optimo, pero encontramos otro mejor. $\square$
## b)
- El algoritmo posee una complejidad temporal de $O(n \ log\ n)$ Pues utiliza sorted que en python es [timsort](https://en.wikipedia.org/wiki/Timsort) y el slicing es $O(k)$
## c)
- Para lograr una complejidad $O(n \ log \ k)$ habría que itilizar heapify con el algoritmo de floyd $O(n)$ y hacer un min-head con los k elementos más grandes hasta el momento.
- Cuando encontras un elemento mayor que el top del min-heap, lo reemplazas y ajustas.
```python
import heapq
def sumaSelectiva(X, k):
minHeap = X[:k]
heapq.heapify(minHeap)
for x in X[k:]:
# Si el elemento actual es mayor que el mínimo en el heap,
# lo reemplazamos y ajustamos el heap.
if x > minHeap[0]:
heapq.heapreplace(minHeap, x)
# Calculamos la suma de los elementos en el min-heap.
max_suma = sum(minHeap)
# Para obtener el subconjunto, convertimos el heap en una lista.
subconjunto = sorted(minHeap) # Esto es solo para tener el subconjunto ordenado.
return max_suma, subconjunto
```