[PYTHON] Optimisation de combinaison - problème typique de problème de sac à dos

Problème typique et méthode d'exécution

Problème de sac à dos

Étant donné un sac à dos d'une capacité de $ c (\ gt 0) $ et $ n $ bagages $ N = \ {1, \ dots, n \} $. Soit la capacité des bagages $ i \ in N $ $ w_i (\ gt 0) $ et la valeur $ p_i (\ gt 0) $. Trouvez l'assortiment de bagages qui maximise la somme des valeurs dans la limite de capacité de $ c $.

Méthode d'exécution

usage

Signature: knapsack(size, weight, capacity)
Docstring:
Problème de sac à dos
Maximisez la valeur
contribution
    size:Liste des tailles de bagages
    weight:Liste des valeurs des bagages
    capacity:capacité
production
Somme des valeurs et liste des numéros de bagages sélectionnés

python

from ortoolpy import knapsack
size = [21, 11, 15, 9, 34, 25, 41, 52]
weight = [22, 12, 16, 10, 35, 26, 42, 53]
capacity = 100
print(knapsack(size, weight, capacity))

résultat

(105.0, [0, 1, 3, 4, 5])

python

# pandas.DataFrame
from ortoolpy.optimization import Knapsack
Knapsack('data/knapsack.csv', 100)

Les données

• data/knapsack.csv