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

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 илиЯва в ваших ответах, пожалуйста.

Answer 1

Как насчет:

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

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

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

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

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