Problème du sac à dos (version gloutonne) — exercice corrigé de Python (école d'ingénieur) (chapitre 2)

Problème du sac à dos (version gloutonne)

Structures de contrôle : conditions et boucles

Énoncé

On dispose d'objets de poids $p_{i}$ et de valeurs $v_{i}$ , et d'un sac de capacité $C$ . La version fractionnaire autorise à prendre des fractions d'objets. Implémenter l'algorithme glouton (trier par rapport valeur/poids) et calculer la valeur maximale.

Corrigé

def sac_a_dos_fractionnaire(poids, valeurs, capacite):
    """
    Retourne la valeur maximale pour le problème du sac à dos fractionnaire.
    Complexité : O(n log n) due au tri
    """
    n = len(poids)
    objets = [(valeurs[i] / poids[i], poids[i], valeurs[i]) for i in range(n)]
    objets.sort(reverse=True) # Tri par rapport valeur/poids décroissant
    
    valeur_totale = 0.0
    capacite_restante = capacite
    
    for ratio, p, v in objets:
        if capacite_restante >= p:
            # Prendre l'objet entier
            valeur_totale += v
            capacite_restante -= p
        else:
            # Prendre une fraction
            fraction = capacite_restante / p
            valeur_totale += fraction * v
            break # Sac plein
            
    return valeur_totale

Exemple :

poids = [10, 20, 30]
valeurs = [60, 100, 120]
capacite = 50
# Ratios : 6.0, 5.0, 4.0
# Ordre : objet 0 (ratio 6.0, poids 10), objet 1 (ratio 5.0, poids 20), objet 2 (ratio 4.0)
# Prendre objet 0 : reste 40, valeur 60
# Prendre objet 1 : reste 20, valeur 160
# Prendre 20/30 de l'objet 2 : valeur 160 + (2/3)*120 = 240

Remarque : L'algorithme glouton est optimal pour la version fractionnaire, mais pas pour la version 0/1 (non fractionnaire).