Помогите решить задачу оптимизации

[Айкон]

Образное описание:
1. Представьте себе трафарет.
2. Теперь, представте что у вас кучка самых разных трафаретов из N штук (N >= 1).
3. Вы складываете их в шляпу, подкидываете ввверх, они удараряются об потолок и падают на пол.
4. Трафаеты раскадало по полу, но многие из них лежат внахлёст один на другой.
5. Суммарная площадь пола накрытая трафаретами - S. Из-за лежащих внахлёст трафаретов S значительно меньше суммарной площади всех трафаретов.

Задача: найти такую минимальную (по количеству штук) комбинацию трафаретов, что они будут покрывать 80% от S.


Исходные данные этой же задачи, но вместо рисунков трафаретов - числа из диапазона [1-10000]:

            var maxValue = 10000;
            var rnd = new Random();
            int trafaretsNum = rnd.Next(1, 100); // количество трафаретов
            int[][] trafarets = new int[trafaretsNum][]; // первый уровень - непосредственно трафарет, второй уровень - точки трафарета
            for (int i = 0; i < trafarets.Length; i++)
            {
                int trafaretSize = rnd.Next(1, 1000); // размер (количество точек) трафарета
                trafarets[i] = new int[trafaretSize];
                for (int j = 0; j < trafarets[i].Length; j++) // заполняем трафарет
                {
                    trafarets[i][j] = rnd.Next(1, maxValue);
                }
            }
            Dictionary<int, object> dict = new Dictionary<int, object>();
            foreach (int[] trafaret in trafarets)  // ищем все накрытые трафаретами точки
            {
                foreach (int val in trafaret)
                {
                    if (!dict.ContainsKey(val))
                    {
                        dict.Add(val, null);
                    }
                }
            }
            int[] S = dict.Keys.ToArray();  // накрытый трафаретами набор чисел.

Необходимо найти такой минимальный набор трафаретов (trafarets[i]), что бы накрыть 80% чисел из массива S.

Задача, на самом деле сугубо практическая и бизнесовая, просто я её максимально выхолостил для простоты понимания.
По возможности нужно максимально производительное решение, т.к. выбор оптимального набора "трафаретов" выполняется на потоке тысячи раз.

Устроит решение на любом из языков: C#, Java, Python.

[evg_m]

сортируем трафареты по их площади
начиная с наибольшего считаем их суммарную площадь.
как только суммарная площадь >=S*0.8 то получили искомое.

минимальная когда нахлесты =0
любая другая комбинация из такого же числа трафаретов будет занимать меньшую площадь.

Задача: найти такую минимальную (по количеству штук) комбинацию трафаретов, что они будут покрывать 80% от S.

Вывод: представлена неполная задача. Или точнее сформулирована не та задача которую нужно решить.

просто я её максимально выхолостил для простоты понимания.

слишком!

В условиях вероятностного(случайного) разброса, НЕВОЗМОЖНО строго сказать о минимальном количестве.
строгий минимум приведен выше

можно говорить о той или иной вероятности покрытия заданной площади (S*0.8) заданным (или случайным) набором.
НО здесь начинается вопрос о характере случайности разброса(нахлеста) разных трафаретов.

[Айкон]

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


Задача сформулирована правильно, мне нужно решение для случайного разброса значений внутри трафаретов.

[evg_m]

все близкие по внутреннему наполнению

а что это такое внутреннее наполнение? В исходной постановке этого понятия не видно.
трафарет либо лежит отдельно, либо накрыт другим.

многие из них лежат внахлёст один на другой.

максимальное покрытие минимальным числом когда нахлестов нет.

мне нужно решение для случайного разброса значений внутри трафаретов.

случайный разброс даже всех трафаретов не гарантирует покрытия заданной площади.

невероятный (с точки зрения "здравого смысла"), но ВОЗМОЖНЫЙ (имеющий ненулевую вероятность) случай.
ВСЕ (случайно) упали так кучно, друг на друга, что площадь покрытия = площади максимального, которая как известно < S*0.8. Иначе не было бы вопроса, так как любой набор содержащий данный максимальный удовлетворяет условию задачи.

можно говорить о той или иной вероятности покрытия заданной площади (S*0.8) заданным (или случайным) набором.

[evg_m]

Итак ваша задача, как я ее понял исходя из кода, а не текстового описания.

Есть некоторое множество S. множество это набор, такой что никакой элемент не может входит дважды. (при объединении они "сливаются")

СЛУЧАЙНЫМ образом генерируется его подмножества T1,...,Tm.
Среди этих подмножеств (случайных, но заданных!) НАДО НАЙТИ минимальное количество таких что их объединение будет покрывать >= 80% от S.

Вы согласны с такой формулировкой вашей задачи?
Если да, то насколько можно отклоняться от требований задачи (минимальность, полнота покрытия) в угоду простоте и скорости?
Есть ли какие-либо ограничения?
например мощность подмножеств (число элементов) не может превышать заданную величину.

В терминах пол, трафарет ваша задача будет такой
Есть пол (множество).
Есть отдельный трафарет (подмножество) общим размером с пол (он может лежать на полу только определенным образом), но заполненный частично, так что закрывает часть пола в соответствии с "рисунком".
Вы берете случайный набор таких трафаретов и выкладываете их на полу одним и тем же фиксированным для них образом.
Надо найти минимальный набор из выбранных(предоставленных), так чтобы было закрыть как минимум 80% пола.

ВАШИ ошибки в в описании (противоречия с кодом)
все трафареты лежат заданным образом, на самом деле все они имеют раму соответствующую полу, т.е. накрывают ВЕСЬ пол, но имеют внутренние случайные вырезы!!!
вы не случайно разбрасываете ВСЕ маленькие квадратики, а случайно берете НЕСКОЛЬКО больших во весь пол трафаретов.
поэтому вопрос об ограничении на размер подмножеств (размер вырезов на трафарете) имеет место быть.

P.S. где-то(на этом или другом форуме) когда-то(давно), я подобную задачу кажется встречал.
а может это был rsdn ?

общий алгоритм решения прост.
0. делаем исходный набор текущим. (теперь текущий состоит из всех "поднаборов" размера 1).
1. берем текущий набор
1.1. исключаем дубли
1.2 сортируем по размеру.
1.3. если лучший покрывает, то определяем из каких исходных он состоит ("вспоминаем" как его собирали) и конец работы.

2. составляем новый набор. (тем самым увеличивая размер "поднабора" на единицу)
2.1. к каждому из текущего набора добавляем каждый из исходного. (по правилам множеств!)
2.2. делаем новый набор текущим и возврат к п.1.
Если есть ограничения, (число наборов, максимальный/минимальный размер набора, .... ) можно думать об улучшениях.

[Айкон]

evg_m, спасибо!
Возможно, будет интересно: чуть более лаконичное описание Вашего решения на RSDN.



Как мне подсказали умные люди, то что я хочу в литературе зовётся как "partial set cover". Я осознал всю губораскатанность своего желания с поиском оптимального решения, обойдусь жадным алгоритмом. Вопрос закрыт.