---
# System prepended metadata

title: TP4 - `m` partitions de `n` entiers

---

# TP4 - `m` partitions de `n` entiers

> L’objet du TP est de résoudre le problème de la partition de `n` entiers en `m` sous-ensembles dont la somme des entiers du plus grand sous-ensemble est la plus petite possible, avec `m` fixé.


## Une solution heuristique avec tas
Un tas est un arbre binaire qui permet de retrouver directement le minimum dans un ensemble d'élements.
On va considérer qu'un noeud représente ici un des `m` sous-ensemble ; et que la racine est toujours le minimum.
Notre algorithme va mettre les `n` entiers dans une pile. A chaque dépilement, la valeur `n` est ajoutée dans le tas.
Au bout de `m` valeurs insérées, la valeur de n est ajoutée dans le plus petit ensemble : la racine.
Ainsi on répartit les `n` entiers dans au plus `m` sous-ensembles les plus petits possibles. Mais c'est une solution heuristique, proche de la vérité et peut mal fonctionner dans certains cas.



## L'algorithme

```python
from heapq import heappop, heappush

class Elem:
  def __init__(self, val, coin):
    self.val = val
    self.coins = []
    self.coins.append(coin)

  def __gt__(self, other):
    return self.val > other.val

def divInM(coins, m):
  heap = []

  goal = sum(coins) / m
  print("Goal : ", goal)

  coins = sorted(coins, reverse=True)

  while(coins):
    currentVal=0
    if heap:
      currentVal = heap[0].val
    
    coin = coins.pop(0)

    if len(heap) < m:
      elem = Elem(coin, coin)
      heappush(heap, elem)
    else:
      total = coin + currentVal
      heap[0].val = total
      heap[0].coins.append(coin)

      # Then sort table
      heap = sorted(heap)

  for e in heap:
    print("----")
    print(e.val)
    print(e.coins)

def main():
  coins = [11,5,7,10,5,6,9]
  divInM(coins, 3)

main()
```