Microsoft 365 Tri liste - répartition égale

[La_Mouette]

Bonjour à tous,
J'ai eu beau me creuser la tête, chercher sur ce forum, je ne trouve pas la méthode qui pourrait répondre à mon problème.

Le voici :

• Je possède une liste d'éléments A1 ; A2 ; etc dont chacun est associé à un nombre (appellons-le poids)
• Chaque élément est unique
• Le nombre d'éléments initial n'est pas fixé (ne dépassera pas une centaine). La liste ne possède que des nombres positifs mais pas entiers.

J'aimerais partitionner ma liste initiale en "paquets" qui ont tous la même somme, cette somme étant fixée (à 39, si cela aide).
Chaque élément a un poids forcément < 39.

• Peu importe le nombre d'éléments final par paquet (un paquet peut avoir 1 seul élément quand un autre en a 12).
• A noter que ma liste initiale sera fait de telle sorte qu'une solution est possible en acceptant des approximations (jusqu'à l'unité).
• Les paquets doivent contenir tous les nombres de la liste initiale.

Un fichier explicatif avec exemple et détails ci-joint.

Merci d'avance pour votre aide ! Formules et/ou macros, selon votre convenance ; je pourrais adapter à mon cas.
Même une idée de méthode m'aiderait.

Edit : une base intéressante sans doute ici https://excel-downloads.com/threads/repartition-equitable.20002192/

 

[vgendron]

hello

une idée

1) tu tries les données (colonne A+B) sur la colonne B en ordre décroissant
==> tu peux déjà en déduire que la somme MIni d'un paquet est la valeur max de la colonne (dans ton exemple 86.3)

2) ensuite , tu selectionnes autant de lignes nécessaire pour atteindre la valeur de 86.03 pour en faire un paquet.. ca donnerait ici 4 paquets..

après.. si la somme demandée est différente. (genre 100): il va falloir trouver un autre algorithme...

fais une recherche sur le forum, je suis prêt à parier qu'il y a déjà eu ce genre de demande

 

[mapomme]

Bonjour à tous,

A noter qu'une solution est possible, forcément, en acceptant des approximations (jusqu'à l'unité).

C'est démontré ça ? Il y a des contre-exemples triviaux me semble-t-il, non ?

edit : les paquets doivent-ils contenir tous les nombres de la liste ?

 

[La_Mouette]

Bonjour à tous,

C'est démontré ça ? Il y a des contre-exemples triviaux me semble-t-il, non ?

edit : les paquets doivent-ils contenir tous les nombres de la liste ?

En effet je suis désolé je me suis mal exprimé.
Je voulais dire que dans mon cas, il y aura forcément une solution (au moins approximativement, càd qu'on peut arrondir les chiffres à l'unité près pour s'arranger), sans aucun doute.
Les paquets doivent en effet contenir tous les nombres de la liste.

 

[La_Mouette]

hello

une idée

1) tu tries les données (colonne A+B) sur la colonne B en ordre décroissant
==> tu peux déjà en déduire que la somme MIni d'un paquet est la valeur max de la colonne (dans ton exemple 86.3)

2) ensuite , tu selectionnes autant de lignes nécessaire pour atteindre la valeur de 86.03 pour en faire un paquet.. ca donnerait ici 4 paquets..

après.. si la somme demandée est différente. (genre 100): il va falloir trouver un autre algorithme...

fais une recherche sur le forum, je suis prêt à parier qu'il y a déjà eu ce genre de demande

Merci vgendron pour l'idée, je vais creuser. La somme de chaque paquet est fixée (et je peux même vous donner la valeur : 39).

J'ai cherché sans succès, mais peut-être mal, je vais re-creuser aussi.

 

[vgendron]

Merci vgendron pour l'idée, je vais creuser. La somme de chaque paquet est fixée (et je peux même vous donner la valeur : 39).

J'ai cherché sans succès, mais peut-être mal, je vais re-creuser aussi.

Hello
un paquet de 39 + toutes les lignes doivent etre utilisées ==> sans meme aller plus loin, je sais déjà que c'est pas possible..
la dernière ligne est à 86...

 

[La_Mouette]

J'ai retrouvé un fil de discussion où l'excellent (sisi il faut le dire, encore merci pour ton implication) mapomme avait déjà beaucoup planché sur ce type de sujet : https://excel-downloads.com/threads/repartition-equitable.20002192/. Dans l'esprit tout est là pour répondre à mon problème.

J'ai effectué quelques tests, et pour mon cas peu m'importe que le nombre de lignes par groupe soit égal, je privilégie que le total soit égal à une somme prédéfinie, je vais voir ce que je peux adapter, pensez-vous que c'est une bonne base ?

 

[La_Mouette]

Hello
un paquet de 39 + toutes les lignes doivent etre utilisées ==> sans meme aller plus loin, je sais déjà que c'est pas possible..
la dernière ligne est à 86...

J'aurais dû donner un exemple sans ce cas, il est tout à fait possible de diviser les éléments (et donc placer 39 de cet élément dans un premier paquet ne comptant qu'un seul élément, 39 dans un deuxième, et le restant (8) dans un troisième paquet qui sera complété par d'autres éléments).
Mais il n'est pas nécessaire de prévoir cela dans une formule/code, je modifierai à la main en entrée.
Et au lieu d'avoir 1 élément A1 = 86, j'en aurais 3 : A1 = 39 ; A1 = 39 ; A1 = 8.

Désolé de n'avoir pas pensé à cela initialement, je modifie le post initial.

Edit : Simplifions le problème, oublions ce cas, je m'arrangerai pour qu'il n'arrive pas.

 

[mapomme]

Re,

J'ai retrouvé un fil de discussion où l'excellent (sisi il faut le dire, encore merci pour ton implication) mapomme avait déjà beaucoup planché sur ce type de sujet : https://excel-downloads.com/threads/repartition-equitable.20002192/. Dans l'esprit tout est là pour répondre à mon problème.

J'ai effectué quelques tests, et pour mon cas peu m'importe que le nombre de lignes par groupe soit égal, je privilégie que le total soit égal à une somme prédéfinie, je vais voir ce que je peux adapter, pensez-vous que c'est une bonne base ?

Alors là, ce fil vieux de 10 ans que tu as déterré était complètement sorti de ma mémoire de moineau.
Il va falloir que je réexamine le code pour voir si on peux éventuellement en tirer quelque chose.
Je n'en suis pas sûr du tout mais sait-on jamais ?

 

[La_Mouette]

Bonjour à tous,
Je me permets de relancer ce post si jamais une bonne âme s'y replonge. J'ai édité le premier post pour y intégrer toutes les précisions nécessaires qui ont émergé des discussions déjà entamées.

Merci d'avance !

 

[laurent950]

Bonsoir Le Forum @vgendron @mapomme @La_Mouette

J'aimerais partitionner ma liste initiale en "paquets" qui ont tous la même somme, cette somme étant fixée (à 39, si cela aide).
Chaque élément a un poids forcément < 39.
Réglage ici dans le code : If sumP > 38 And sumP < 39 Then

Donnée en colonne
A et B de votre fichier en Poste #1

Résultat en colonne D:F

Option Explicit

Sub PartitionnerListeCourt()
    Dim ws As Worksheet: Set ws = ThisWorkbook.Sheets("Feuil1")
    Dim lastRow As Long: lastRow = ws.Cells(ws.Rows.Count, 1).End(xlUp).Row
 
    Dim elems() As Variant, poids() As Variant
    elems = ws.Range("A1:A" & lastRow).Value
    poids = ws.Range("B1:B" & lastRow).Value
 
    ' Collection de paquets
    Dim paquets As Collection: Set paquets = New Collection
    Dim i As Long, j As Long, trouve As Boolean
 
    For i = 1 To UBound(poids, 1)
        trouve = False
        For j = 1 To paquets.Count
            Dim p As Collection: Set p = paquets(j)
            Dim s As Double: s = 0
            Dim e As Variant
            For Each e In p: s = s + e(1): Next
            If s + poids(i, 1) <= 39 Then
                Dim arr(1 To 2): arr(1) = poids(i, 1): arr(2) = elems(i, 1)
                p.Add arr
                trouve = True
                Exit For
            End If
        Next j
        If Not trouve Then
            Dim np As Collection: Set np = New Collection
            Dim arr2(1 To 2): arr2(1) = poids(i, 1): arr2(2) = elems(i, 1)
            np.Add arr2
            paquets.Add np
        End If
    Next i
 
    ' Affichage
    Dim ligne As Long: ligne = 1
    For i = 1 To paquets.Count
        Dim sumP As Double: sumP = 0
        Dim LigCol As String: LigCol = ""
        For Each e In paquets(i)
            LigCol = LigCol & e(2) & " "
            sumP = sumP + e(1)
        Next
        If sumP > 38 And sumP < 39 Then
            ws.Cells(ligne, 4).Value = "Paquet " & i
            ws.Cells(ligne, 5).Value = LigCol
            ws.Cells(ligne, 6).Value = sumP
            ligne = ligne + 1
        End If
    Next i
End Sub

 

[La_Mouette]

Bonsoir Laurent,
Merci énormément pour ce travail considérable ! Je vais prendre le temps de regarder cela dans les prochains jours pour vous faire un retour éclairé.