Problème de fractionnement typique de la combinaison de problèmes

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

Définir le problème de division

$ N $ Sous-ensemble de l'ensemble $ M = \ {1, \ dots, m \} $ $ S_j (\ subseteq M), j \ in N = \ {1, \ dots, n \} Supposons qu'un coût de $ c_j $ soit donné à $. Trouvez la division $ X (\ subseteq N) $ de $ M $ qui minimise la somme des coûts. Le fractionnement ne doit pas avoir les mêmes éléments dans le sous-ensemble.

Méthode d'exécution

usage


Signature: set_partition(n, cand)
Docstring:
Définir le problème de division
contribution
    n:Nombre d'éléments
    cand: (poids,Sous-ensemble)Liste des candidats
production
Liste des numéros de la liste des candidats sélectionnés

python


#Données CSV
import pandas as pd
from ortoolpy import set_partition
ss = pd.read_csv('data/subset.csv')
g = ss.groupby('id')
set_partition(len(g), [(r.weight.iloc[0], r.element.tolist()) for _, r in g])

résultat


[2, 3]

set.gif

python


# pandas.DataFrame
from ortoolpy.optimization import SetPartition
SetPartition('data/subset.csv')
id weight element
4 2 1.0 a
5 2 NaN d
6 3 3.0 b
7 3 NaN c

python


#Exemple de données
from ortoolpy import set_partition
set_partition(4, [(1, ('a', 'b')), (1, ('a', 'c')), (1, ('a', 'd')), (3, ('b', 'c'))])

résultat


[2, 3]

Les données

Recommended Posts

Problème de fractionnement typique de la combinaison de problèmes
Un exemple très simple de problème d'optimisation avec ortoolpy
[At Coder] Résoudre les problèmes typiques de la recherche de priorité en profondeur (DFS)
Combinaison optimisation-problème typique-problème d'ensemble stable maximum
La puissance des solveurs d'optimisation combinée
Méthode de planification des expériences et optimisation des combinaisons
Optimisation des combinaisons - Problème typique - Problème d'itinéraire de transport (optimisation de la livraison)
Essayez de résoudre un problème défini de mathématiques au lycée avec Python
Un ensemble d'entiers qui satisfait ax + by = 1.
Trouver la main de "Millijan" par l'optimisation des combinaisons
Résolution du problème N Queen avec l'optimisation continue / combinée
Résolution du problème N Queen avec l'optimisation des combinaisons
Minimisez le nombre de polissages en optimisant la combinaison
Juger la finition du mahjong par l'optimisation des combinaisons
Utiliser l'optimisation des combinaisons
(Python) Traite les valeurs entières comme un ensemble d'indicateurs
[GoLang] Définissez un espace au début du commentaire
[At Coder] Résolution d'un problème BFS typique [A - Darker and Darker]
Le problème Zip 4 Gbyte est une histoire du passé