# PB Sac à dos
from random import randint
from copy import deepcopy
## Définition de l'ensemble des objets
Mmax = 8 # masse maximale
Vmax = 8 # valeur maximale
N = 5 # nombre d'objets différents
l_noms = ['balle', 'boite', 'casserole', 'fleur', 'montre', 'javelot', 'bibelot',
'perceuse', 'stylo', 'guitare','livre de SII', 'ordinateur', 'photo de Johnny Depp',
'appareil photo', 'manette de PS4','santon', 'paquet de mouchoirs', 'ornithorynque',
'oreiller', 'baskets']
#l_objets = [ (l_noms[i],randint(1,Mmax), randint(1,Vmax)) for i in range(N) ]
l_objets = [('balle', 8, 4), ('boite', 6, 6), ('casserole', 8, 3), ('fleur', 6, 2), ('montre', 1, 7)]
l1 = deepcopy(l_objets)

## 1 Fonctions utilitaires

def calculValeur(liste_Objets: list)->int:
    ''' argument liste_Objets: tuple (nom, masse, valeur) '''
    valeur_totale = 0
    for i in range(len(liste_Objets)):
        valeur_totale += liste_Objets[i][2]
    return valeur_totale

def calculMasse_rec(liste_Objets: list)->int:
    # condition d'arret
    if liste_Objets == []:
        return 0
    return liste_Objets[0][1] + calculMasse_rec(liste_Objets[1:])

def triParRatio_rec(liste_Objets: list)->int:
    ''' argument liste_Objets: tuple (nom, masse, valeur)
        tri par ratio valeur/masse croissant
    '''
    # condition d'arret
    if liste_Objets == []:
        return []
    ratioObjets = [obj[2]/obj[1] for obj in liste_Objets]
    # recheche ind_ratio_min
    min_ratio = float('inf')# valeur infinie
    for ind_ratio in range(len(ratioObjets)):
        if ratioObjets[ind_ratio] < min_ratio:
            min_ratio = ratioObjets[ind_ratio]
            ind_ratio_min = ind_ratio
    objet_min = liste_Objets.pop(ind_ratio_min)
    return [objet_min] + triParRatio_rec(liste_Objets)

### Méthode gloutonne

def glouton_ratio(liste_Objets: list,cmax:int)->list:
    '''
    arg: liste_Objets non triée
    return:  liste [valeurTotale, liste_choixObjets]
    liste_Objets: tuple (nom, masse, valeur)
    '''
    list0 = deepcopy(liste_Objets)
    list_triee = triParRatio_rec(list0)
    liste_choixObjets = [] # init
    valeurTotale = 0 # init

    for i in range(len(list_triee)-1,-1,-1):
        if list_triee[i][1] < cmax:
            cmax -= list_triee[i][1]
            liste_choixObjets.append(list_triee[i][0])
            valeurTotale += list_triee[i][2]

    return [valeurTotale, liste_choixObjets]

## 3. Aglorithme glouton fractionnaire version avec DICTIONNAIRE
dic_fruits =  {'Framboises': (1,24), 'Mures': (5,3), 'Myrtilles': (3,16), 'Fraises': (5,6),'Groseilles': (1,13)}

dic1 = deepcopy(dic_fruits)

def triParPrixkg_rec(dico_fruits):
    dico = deepcopy(dico_fruits)
    # evite d'effacer dico_fruits, finalement au bon endroit ;)
    # condition d'arrêt
    if  dico == {}:
        return []

    min_prixkg = float('inf')
    for (fruit,data) in dico.items():
        if data[1] < min_prixkg:
            min_prixkg = data[1]
            fruit_min = fruit # string
    del dico[fruit_min]
    return [fruit_min] + triParPrixkg_rec(dico)

def glouton_Masse(dico_fruits:dict, cmax:int)->list:
    '''
    argument: dico_fruits = {'NomFruit': (masse, prixKg),...}
    return: liste = [[choixFruits, masse],...]
    '''
    dico = deepcopy(dico_fruits)
    liste_fruits_triee = triParPrixkg_rec(dico)
    n = len(liste_fruits_triee)
    liste_choixFruits = []
    valeurTotale = 0
    for i in range(n):
        masseFruit = dico[liste_fruits_triee[n-1-i]][0]
        prixKgFruit = dico[liste_fruits_triee[n-1-i]][1]
        if masseFruit < cmax:
            cmax -= masseFruit
            liste_choixFruits.append([liste_fruits_triee[n-1-i],masseFruit])
            valeurTotale += masseFruit * prixKgFruit
        else:
            masseFruit = cmax
            liste_choixFruits.append([liste_fruits_triee[n-1-i],masseFruit])
            valeurTotale += masseFruit * prixKgFruit
            cmax = 0
    # sans partition:
    return [valeurTotale, liste_choixFruits]

## 3- Algorithme Glouton Fractionnaire version avec des LISTES
cueillette = [ ["fraises",5,6],["framboises",1,24], ["myrtilles",3,16],  ["mures",2,3], ["groseilles",1,13] ]


def triParPrixKg2(liste_Objets :list)->list:
    """rangement par ordre décroissant des prix par kilo"""
    l_etud = deepcopy(liste_Objets)
    n = len(l_etud)
    for i in range(n-1):
        for j in range(i+1,n):
            if l_etud[j][2] > l_etud[i][2] :
                l_etud[j], l_etud[i] = l_etud[i], l_etud[j]
    return l_etud


def glouton_Masse2(liste_fruits:list,cmax:int)->list:
    valeur_sac = 0
    liste_choix = []
    prixkg_tries = deepcopy(triParPrixKg2(liste_fruits))
    capacite = cmax
    n=len(prixkg_tries)
    for i in range(n):
        if prixkg_tries[i][1] <= capacite:
            capacite -= prixkg_tries[i][1]
            liste_choix.append([prixkg_tries[i][0],prixkg_tries[i][1]])
            valeur_sac += prixkg_tries[i][1] * prixkg_tries[i][2]
        else:
            liste_choix.append([prixkg_tries[i][0],capacite])
            valeur_sac += prixkg_tries[i][2] * capacite
            capacite = 0
    return [valeur_sac,liste_choix]