Remplissage en ligne

Question

Supposons que nous ayons 3 ensembles $ a, b, c $ qui peuvent contenir un maximum de deux éléments, chacun. Ainsi, le nombre total d'éléments que les ensembles peuvent maintenir ensemble la capacité totale (TC) est de 3 $ * 2 = 6 $.

Maintenant, les éléments arrivent en série (un par un) avec certaines propriétés qui imposent les contraintes suivantes:

E1 : Can be placed in either A or B but not C.
E2 : Can be placed in either B or C but not A.
E3 : Can be placed in either A or C but not B.
E4 : Can be placed in only B.

Étant donné que nous n'avons aucune connaissance préalable sur ces éléments, le défi consiste à distribuer ces éléments dans les ensembles $ a, b, c $ tels que les propriétés sont satisfaites.

Ici, nous pouvons voir que le nombre total d'éléments entrants est de 4 $ et TC est de 6 $.

Hypothèse : Il existe toujours une solution réalisable

Question : Quelle approche algorithmique convient à cette situation? Encore une fois, je souligne que nous n'avons pas a priori Connaissance des éléments.