Online Set Filling
-
05-11-2019 - |
سؤال
Suppose we have 3 sets $A, B, C$ which can can hold a maximum of two elements, each. So the total number of elements that the sets can hold together i.e. total capacity (TC) is $ 3*2 = 6$.
Now, elements arrive serially (one-by-one) with some properties that impose the following constraints:
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.
Given that we have no prior knowledge about these elements, the challenge is to distribute these elements into the sets $A, B, C$ such that the properties are satisfied.
Here we can see that the total number of incoming elements are $4$ and TC is $6$.
Assumption : There always exists a feasible solution
Question : What algorithmic approach is appropriate for this situation? Again I stress that we have no apriori knowledge about the elements.
لا يوجد حل صحيح