Назначения с минимальными долями

Question

Скажем, у нас есть ряд элементов E и ряд комплектов S.

нам нужно назначить элементы наборов таким образом, чтобы:

1. Все наборы примерно содержат одинаковое количество элементов (минимальное разницу в заданной величины между наименьшим и наибольшим набором)
2. Число элементов для каждого набора должно быть как можно меньше.
3. Каждому элементу необходимо присвоить не менее минимальный% от общего числа. Это% задается для каждого элемента (это означает, что элементы конечно быть отнесены к нескольким наборам соответственно)

Заметим, что (1) и (2) являются проблемными задачами, а в некоторых случаях существует компромисс между ними. Я эффективно ищу математическую формулировку/решение, которое параметризует этот компромисс. Между тем (3) является просто проблемой ограничения.

Как найти оптимальное назначение? Имеет ли эта проблема название в литературе? В случае, если это имеет значение, я специально ищу решение в Python.

---

В качестве примера, скажем, у нас есть 3 комплекта и 10 элементов, каждый из них с указанием мин. часть множеств следующим образом:

0  97.844356 
1  48.006223 
2  99.772135 
3  16.899074 
4  0.111023 
5  1.028894 
6  5.315590 
7 100.000000 
8  99.838698 
9  93.323315 

Answer 1

Вы только могли вращаться бесконечно над множествами, чтобы определить следующий набор для назначения. Тогда для каждого элемента рассчитать, сколько наборов он должен быть назначен, а затем выполнить задание соответственно:

from itertools import cycle 
from math import ceil 

elems = [ 
    [0, 97.844356], 
    [1, 48.006223], 
    [2, 99.772135], 
    [3, 16.899074], 
    [4, 0.111023], 
    [5, 1.028894], 
    [6, 5.315590], 
    [7, 100.000000], 
    [8, 99.838698], 
    [9, 93.323315] 
] 

def assign(elements, n): 
    sets = [[] for _ in range(n)] 
    gen = (e for e, p in elements for _ in range(ceil(p*n/100))) 

    for s, e in zip(cycle(sets), gen): 
     s.append(e) 

    return sets 

print(assign(elems, 3)) 

Выход:

[[0, 1, 2, 4, 7, 8, 9], [0, 1, 2, 5, 7, 8, 9], [0, 2, 3, 6, 7, 8, 9]] 

В выше cycle используется для перебора бесконечно более целевых множеств. gen представляет собой генератор, который возвращает минимальное количество элементов, чтобы добавить на основе вероятностей:

>>> n = 3 
>>> gen = (e for e, p in elems for _ in range(ceil(p*n/100))) 
>>> list(gen) 
[0, 0, 0, 1, 1, 2, 2, 2, 3, 4, 5, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9] 

Наконец zip используется для генерации (target set, element) кортежей, которые затем присвоенных в пределах цикла.