Sac à dos fractionnaire détaillé

def sac_fractionnaire_detail(objets, capacite):
    objets = sorted(objets, key=lambda o: o[1] / o[0], reverse=True)
    reste = capacite
    choix = []          # (poids, valeur, fraction)
    valeur_totale = 0.0
    for poids, valeur in objets:
        if reste <= 0:
            break
        fraction = min(1.0, reste / poids)
        choix.append((poids, valeur, fraction))
        valeur_totale += valeur * fraction
        reste -= poids * fraction
    return valeur_totale, choix

v, c = sac_fractionnaire_detail([(10, 60), (20, 100), (30, 120)], 50)
print(v)   # 240.0
print(c)   # [(10, 60, 1.0), (20, 100, 1.0), (30, 120, 0.666...)]