L=[ [8,9,"C1"] , [8.45,10.3,"C2"] , [8.1,11.3,"C3"] , [11.15,11.45,"C4"] , [12,12.45,"C5"] , [11,13,"C6"] , [12.3,14,"C7"] , [16,17,"C8"] , [15,18,"C9"] ,[16.3,18.1,"C10"]]


#------Réponse aux question 2 et 3 - codez-ci-dessous--------------------------
def choix_conferences( C ) :
    planning = [C[0]]
    fin=C[0][1]
    for i in range(1,len(C)):
        if C[i][0] >= fin:
            planning.append(C[i])
            fin = C[i][1]
    return planning

resultat = choix_conferences(L)




#------Réponse aux questions 4 et 5 - codez-ci-dessous-------------------------

cueillette = [ [24,1,"framboises"], [16,3,"myrtilles"], [6,5,"fraises"], [3,2,"mures"] ]


def sac_a_dos( L , capacite ):
    masse_sac = 0
    sac=[]
    i=0
    valeur = 0
    while masse_sac < capacite and i < len(L):
        fruit = L[i]
        capacite_restante = capacite - masse_sac
        if fruit[1] > capacite_restante :
            fruit[1] = capacite_restante
        sac.append(fruit)
        valeur = valeur + fruit[1]*fruit[0]
        masse_sac = masse_sac + fruit[1]
        i=i+1
    return sac

def sac_a_dos(L,capacite):
    """Implémentation de la résolution di problème du sac à dos
    L est une liste des éléments à mettre dans le sac
    capacité est la masse maximale qu peut transporter le sac à dos.
    """
    masse_sac = 0
    sac=[]                                        #à l'initialisation, le sac est vide
    i=0                                           #i sert d'indice dans la liste L
    valeur = 0                                    #vaeur du chargement
    
    while .................. and ................:#tant qu'on n'a pas parcouru toute la cueillette 
                                                  #et que la masse du sac n'a pas atteint sa capacité                              
        fruit = L[i]   
        capacite_restante = capacite - masse_sac                           
        if ......................................:#si la quantité du i-eme fruit est supérieure à 
                                                  #la capacité restante du sac

            fruit[1] = .........................  #on modifie la quantité de fruit pour n'en prendre
                                                  #que la quantité correspondant à la capacité restante
                                                  
        sac. ..............(fruit)                #On met le fruit dans le sac
        valeur = valeur + ....................    #On calcule la nouvelle valeur du chargement
        masse_sac = masse_sac + ..............    #On calcule la nouvelle masse du sac
        i=i+1                                     #On incrément i pour passer au fruit suivant de 
                                                  #la cueillette
    return sac
            
        
fruits_ramenes = sac_a_dos(cueillette,5)        
        
   
#------Réponse à la question 6 - codez-ci-dessous------------------------------    

fruits_disponibles = [ [3,1,"melon de cavaillon"], [2.5,2,"melon jaune"], [2,3,"pastèque"] ]

        
def sac_a_dos_nonFractionnaire( L , capacite ):
    masse_sac = 0
    sac=[]
    i=0
    valeur = 0
    while masse_sac+L[i][1] <= capacite and i < len(L):
        fruit = L[i]
#        capacite_restante = capacite - masse_sac
#        if fruit[1] > capacite_restante :
#            fruit[1] = capacite_restante
        sac.append(fruit)
        valeur = valeur + fruit[1]*fruit[0]
        masse_sac = masse_sac + fruit[1]
        i=i+1
    return sac 
        
fruits_ramenes = sac_a_dos_nonFractionnaire(fruits_disponibles,5)        
        
#------Réponse à la question 7 -----------------------------------------------  
""" le résultat obtenu est [[3, 1, 'melon de cavaillon'], [2.5, 2, 'melon jaune']]. 
Ce chargement a pour valeur 1*3+2*2.5=8€. Cette solution n'est pas optimale puisque 
la solution [[2.5,2,"melon jaune"], [2,3,"pastèque"]] a une valeur de 2*2.5+3*2=11€
"""    
        
#------Réponse à la question 8 -----------------------------------------------        
        
"""
Cette version du problème présente bien la propriété de sous-structure optimale:
    Si on considère le sous-ensemble Sk, constitué de k-1 éléments de la solution optimale S,
    L'ensemble C des fruits disponibles est alors ôté des éléments de Sk, ce qui amène à l'ensemble appelé Ck. 
    Ck est le sous problème, et la solution optimale pour ce sous problème fait partie de la solution optimale 
    du problème global.
En revanche, la propriété du choix glouton n'est pas respectée. On a bien vu que le choix glouton du fruit de 
plus grande valeur massique nous a éloigné de la solution optimale {melon jaune , pastèque}.
"""

#------Réponse aux questions 11 et 12 -----------------------------------------  

S=[500,200,100,50,20,10,5,2,1] 

def rendu_monnaie(..................):
    ..... à compléter
    

def rendu_monnaie(valeur,systeme):
    i=0
    K=[0]*len(systeme)
    a_rendre= []
    while valeur >0 :
        if valeur < systeme[i]:
            i=i+1
        else:
            K[i]=K[i]+1
            valeur=valeur-systeme[i]
            a_rendre.append(systeme[i])
    return a_rendre
            


resultat=rendu_monnaie(63,S)

#------Réponse à la question 13 -----------------------------------------------  
S2=[9,7,3,1]
resultat=rendu_monnaie(14,S2)


#------Réponse à la question 14 -----------------------------------------------
"""Les conférences doivent être ordonées ordre décroissant des dates de début
"""


#------Réponse à la question 15 -----------------------------------------------
from operator import itemgetter
L=[ [8,9,"C1"] , [8.45,10.3,"C2"] , [8.1,11.3,"C3"] , [11.15,11.45,"C4"] , [12,12.45,"C5"] , [11,13,"C6"] , [12.3,14,"C7"] , [16,17,"C8"] , [15,18,"C9"] ,[16.3,18.1,"C10"]]
L=sorted(L,key=itemgetter(0),reverse=True)


def choix_conferences( C ) :
    planning = [C[0]]
    debut=C[0][0]
    for i in range(1,len(C)):
        if C[i][1] <= debut:
            planning = [C[i]] + planning
            debut = C[i][0]
    return planning

resultat = choix_conferences(L)

"""Le résultat obtenu est 
[[8.45, 10.3, 'C2'],
 [11.15, 11.45, 'C4'],
 [12.3, 14, 'C7'],
 [16.3, 18.1, 'C10']]
Ce n'est pas le même résultat qu'en débu de sujet, mais c'est un résultat de 
même taille. C'est donc une autre solution optimale
"""