Discussion :

[nebuchad34]

Bonsoir,

je me creuse la tête depuis quelques heures déjà je ne m'en sort pas. Et comme je pense que nombre d'entre vous sauront résoudre ça en un rien de temps je me permet de vous consulter.

Admettons que j'ai N objets à ranger dans des boites. je dispose d'un nombre illimité de boites. mais je sais qu'une boite ne peut contenir que n objets.
De plus, je veux que la répartition soit à peu près homogène.

Par exemple. Si j'ai 10 objets, et des boites de capacités 3 objets.
et bien l'algorithme doit me dire que j'ai besoin de 5 boites de 2 objets, et pas 3 boites de 3 objets et 1 autre de 1 objet.

Pour comprendre, la finalité c'est répartir une liste de joueurs autour de tables de poker...

Voilà, si l'un d'entre vous a une idée, je suis preneur.

Merci

[ToTo13]

Bonsoir,

est ce que tu as essayé de résoudre ce problème en calculant le PPCM ?
Car ton problème c'est bien de trouver le plus petit commun multiple entre tes N objets et une valeur inférieure ou égale à n.

[pseudocode]

Par exemple. Si j'ai 10 objets, et des boites de capacités 3 objets.
et bien l'algorithme doit me dire que j'ai besoin de 5 boites de 2 objets, et pas 3 boites de 3 objets et 1 autre de 1 objet.

il me semble que Tidus159 a tout récemment ouvert une discussion sur le partitionnement d'entiers.

10 = 10*1 = 5*2 = 3*3 + 1*1 = 2*3 + 2*2 = ...

[Zavonen]

J'aurais vu cela comme ça:
Pour chaque table i ni = maximum de joueurs pouvant prendre place à la table i.
N = nombre total de joueurs à disposer
M= somme des ni = nombre maximal de joueurs pouvant être installés.
Si N>M impossible
Si N<M
Calculer le rapport réel k= M/N <1
Pour chaque table calculer l'optimum oi=int(ni*k)+1
Saupoudrer ensuite les N joueurs un par un sur les tables en arrêtant la distribution pour chaque table pour lequel oi est atteint.

[pseudocode]

On dirait une diffusion d'erreur, à la bresenham...

10 joueurs, avec des tables de 3 => il faut 4 tables => 2.5 joueurs par table

Table #1: il faudrait 2.5 joueurs -> on en met 2 -> delta: +0.5
Table #2: il faudrait 2.5+0.5 = 3 joueurs -> on en met 3 -> delta: 0
Table #3: il faudrait 2.5 joueurs -> on en met 2 -> delta: +0.5
Table #4: il faudrait 2.5+0.5 = 3 joueurs -> on en met 3 -> delta: 0

Résultats: Tables={2,3,2,3}