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)
size weight
0 21 22
1 11 12
3 9 10
4 34 35
5 25 26

Les données

Recommended Posts

Optimisation de combinaison - problème typique de problème de sac à dos
Optimisation de combinaison - problème typique - problème de couverture de vertex minimum
Problème de correspondance stable aux problèmes typique d'optimisation de combinaison
Problème d'optimisation de combinaison-problème typique d'emballage de bac
Optimisation de combinaison - problème typique de correspondance de problème maximum
Optimisation des combinaisons - Problème typique - Problème d'allocation secondaire
Combinaison d'optimisation-problème typique-problème de chemin le plus court
Optimisation combinée - problème typique d'enchères combinées
Combinaison d'optimisation-problème typique de couverture d'agrégat
Problème de correspondance typique de problème-poids par optimisation de combinaison
Problème d'optimisation de combinaison-problème typique de placement des installations
Optimisation de la combinaison - problème typique de l'atelier de travail
Optimisation de la combinaison - problème typique - problème de coupe maximale
Optimisation de combinaison - Problème typique - Problème de vendeur circulaire
Problème d'ordonnancement de travail-problème typique d'optimisation de combinaison
Optimisation de combinaison - problème typique - problème d'arborescence de surface minimale
Combinaison optimisation-problème typique-problème d'ensemble stable maximum
Optimisation de la combinaison - problème typique - problème de flux de coût minimal
Optimisation de combinaison-problème typique-problème de livraison postale chinoise
Optimisation des combinaisons - Problème typique - Problème d'itinéraire de transport (optimisation de la livraison)
Problème d'optimisation de la combinaison - coupe minimale
Optimisation des combinaisons - Problème typique - Problème de placement des installations sans contrainte de capacité
Combinaison de problèmes typiques d'optimisation et comment le faire