Diviser les objets entre les tableaux avec des contraintes

Question

Disons que nous avons un ensemble d'objets a1, a2, ... un

Et nous avons des tableaux g1, g2, ... g qui peut éventuellement chacun des vides seulement à certains des objets et doit contenir un nombre spécifique d'objets, par exemple: doit contenir 2 objets

g2 peuvent inclure [a5, a6, a7

• g1 peut comprendre [a1, a5, a8], a9, a10] doit contenir 3 objets
• ...
• g peut inclure [a1, a6, a8, a10] doit contenir 4 objets

Quel est le meilleur algorithme pour vérifier s'il est possible de distribuer des objets entre les tableaux (il est nécessaire d'utiliser tous les objets) avec les contraintes mentionnées ci-dessus et pour obtenir cette distribution si possible?

Answer 1

Il est un problème de flux Comment

1. Supposons que nous avons une source S qui a un bord à chaque Ai avec une capacité = 1

2. Il y a un bord de Ai à Gj si Gj peut inclure Ai . La capacité serait égale à 1

3. Leur bord est de Gj à Sink d'une capacité égale à la valeur qu'il doit avoir.

4. Maintenant, si nous exécutons max flow, chaque Ai serait mappé à un Gj. Le débit total devrait être égal à la somme des poids de Gj à couler.
5. Si la somme est valide, il suffit d'obtenir les mappages dans le flux. sinon il est invalide

Answer 2

Soit n le nombre total d'objets et m le nombre total de tableaux.

x=n; 
y=m+1; 
arangement_possible=true; 
while(y>=2) 
{ 
    if(x<=0) 
    { 
     arrangement_possible = false; 
     break; 
    } 
    x=x-y; 
    y=y-1; 
} 

Si la disposition possible est vraie alors une telle disposition est possible sinon.

ou

chk pour cette condition

(((m (m + 1))/2) -1) = n <