Как найти минимальное количество непересекающихся подмножеств с максимальной суммой и размером

Question

Я ищу, чтобы найти минимальное количество непересекающихся подмножеств (мы будем обозначать эти b_i) из набора (мы будем обозначать X) такой что все b_i удовлетворить следующие ограничения:

• Каждый элемент x_i из X должны быть помещены ровно в одну партию.
• len(b_i) <= MAX_ELEMENTS_PER_BATCH для всех i
• sum(b_i) <= MAX_SUM_PER_BATCH для всех i

Я придумал эвристику для поиска партий, которые удовлетворяют ограничениям, но это не гарантирует минимальное количество партий.

Например:

1. Сортировать коллекцию.
2. Возьмите самый большой элемент и вставьте его в свою партию.
3. Заполните пакет наименьшими элементами, пока добавление следующего элемента не приведет к превышению суммы пакета MAX_SUM_PER_BATCH,
4. Удалить элементы из этой партии из коллекции
5. Повторите шаги 2-4, пока не останется никаких элементов.

Я понимаю, что это, вероятно, решаемая проблема с каким-то именем, о котором я не знаю, и что оптимизация для минимального количества партий вносит здесь сложность.

Псевдокод, python или java в ваших ответах, пожалуйста.

Answer 1

Как насчет:

1. Сортировать коллекцию (от самой большой до самой маленькой)

2. Возьмите следующий элемент коллекции и попробуйте вписать его в существующие партии (начиная с первого созданного пакета) на основе 2 правил.

3. Если подходит, добавьте в пакет и вернитесь к 2. В противном случае создайте новый пакет, добавьте к нему и вернитесь к 2

Я считаю, что он удовлетворяет всем условиям, и нужно только 1 линейный проход для коллекции после сортировки

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