from itertools import chain, combinations
import time

conjuntoEjercicioUno = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
conjuntoEjercicioDos = {0, 1, 2}

def crearSubconjuntos(iterable):
    """Crea todos los subconjuntos posibles a partir de un conjunto de elementos."""
    s = list(iterable)
    return chain.from_iterable(combinations(s,r) for r in range(len(s)+1))

class elemento:
    """Objeto elemento (objetos a introducirse en la mochila)."""

    def __init__(self, cod, vol, val):
        self.codigo = cod
        self.volumen = vol
        self.valor = val
        self.rvv = val/vol

    def getCod(self):
        return self.codigo

    def getVol(self):
        return self.volumen

    def getVal(self):
        return self.valor

    def getRVV(self):
        return self.rvv

    def mostrarObjeto(self):
       print("ID: ", self.codigo, ", Volumen: ", self.volumen, ", Valor: ", self.valor)

def iniciarElementosUno():
    """Valores de los elementos del ejercicio apartado 1."""
    elementos = []
    obj1 = elemento('1', 150, 20)
    obj2 = elemento('2', 325, 40)
    obj3 = elemento('3', 600, 50)
    obj4 = elemento('4', 805, 36)
    obj5 = elemento('5', 430, 25)
    obj6 = elemento('6', 1200, 64)
    obj7 = elemento('7', 770, 54)
    obj8 = elemento('8', 60, 18)
    obj9 = elemento('9', 930, 46)
    obj10 = elemento('10', 353, 28)
    elementos.extend((obj1, obj2, obj3, obj4, obj5, obj6, obj7, obj8, obj9, obj10))
    return elementos

def iniciarElementosDos():
    """Valores de los elementos del ejercicio apartado 1."""
    elementos = []
    obj1 = elemento('1', 1800, 72)
    obj2 = elemento('2', 600, 36)
    obj3 = elemento('3', 1200, 60)
    elementos.extend((obj1, obj2, obj3))
    return elementos

def busExhaustiva(conjunto, volMochila):
    """Ejecición y muestra de resultados de la búsqueda exhaustiva."""
    start = time.time()
    subconjuntos = crearSubconjuntos(conjunto)
    subOrd = sorted(subconjuntos)
    if conjunto == conjuntoEjercicioUno:
        elementos = iniciarElementosUno()
    else:
        elementos = iniciarElementosDos()
    valor = 0
    indiceMayor = int
    for x in range(0, len(subOrd)):
        volTotal = 0
        valTotal = 0
        for y in range (0, len(subOrd[x])):
            volTotal += elemento.getVol(elementos[subOrd[x][y]])
            valTotal += elemento.getVal(elementos[subOrd[x][y]])
            if volTotal <= volMochila and valTotal > valor:
                valor = valTotal
                indiceMayor = x
    valorTotal = 0
    volumenTotal = 0
    for i in range(0, (len(subOrd[indiceMayor]))):
        elemento.mostrarObjeto(elementos[subOrd[indiceMayor][i]])
        valorTotal += elemento.getVal(elementos[subOrd[indiceMayor][i]])
        volumenTotal += elemento.getVol(elementos[subOrd[indiceMayor][i]])
    end = time.time()
    print('Valor: ', valorTotal)
    print('Volumen: ', volumenTotal)
    print('Tiempo total de ejecucion:', end - start, 'segundos.')
    return

def busHeuristica(conjunto, volMochila):
    """Ejecución y muestra de los resultados de la búsqueda heurística (greedy)."""
    start = time.time()
    if conjunto == conjuntoEjercicioUno:
        elementos = iniciarElementosUno()
    else:
        elementos = iniciarElementosDos()
    elemOrd = sorted(elementos, key=lambda elemento: elemento.rvv, reverse=True)
    elemMochila = []
    valor = 0
    volumen = 0
    for x in range (0, len(elemOrd)):
        if (volumen + elemento.getVol(elemOrd[x]) <= volMochila):
            volumen += elemento.getVol(elemOrd[x])
            elemMochila.append(elemOrd[x])

    for y in range (0, len(elemMochila)):
        elemento.mostrarObjeto(elemMochila[y])
        valor += elemento.getVal(elemMochila[y])
    end = time.time()
    print('Volumen: ', volumen)
    print('Valor: ', valor)
    print('Tiempo total de ejecucion:', end - start, 'segundos.')
    return

def main():
    """Menú de opciones del ejercicio."""
    op = 5
    while op != 0:
        print('MENU: \n'
              '1.- Exhaustivo (1A)\n'
              '2.- Heuristico (1A)\n'
              '3.- Exhaustivo variante (2A)\n'
              '4.- Exhaustivo variante (2B)\n'
              '0.- SALIR \n')
        op = int(input('Seleccione una opción: '))
        print('\n')
        if op == 1:
            busExhaustiva(conjuntoEjercicioUno, 4200)
        if op == 2:
            busHeuristica(conjuntoEjercicioUno, 4200)
        if op == 3:
            busExhaustiva(conjuntoEjercicioDos, 3000)
        if op == 4:
            busHeuristica(conjuntoEjercicioDos, 3000)
        if op ==0:
            break
        print('\n')
        input("Presione enter para continuar")
        print('\n \n')
    return ()

main()