У меня есть определенная подзадача, для которой у меня возникают проблемы с оптимальным решением. Эта проблема похожа на группу сумм подмножеств задач, а также на проблемы заполнения пространства, но я не видел эту конкретную проблему в любом месте. Мне не обязательно нужно оптимальное решение (поскольку я относительно уверен, что это NP-жесткий), но эффективного и быстрого приближения, безусловно, было бы достаточно.Немногие подмножества с суммой меньше N
Проблема: Учитывая список положительных нормированных чисел найти наименьшее число непересекающихся подмножеств, содержащих весь список целых чисел, где каждое подмножество сумм до менее чем N. Очевидно, не целое число в исходном списке не может быть больше, чем N.
В моем приложении у меня много списков, и я могу объединить их в столбцы матрицы, пока они вписываются в матрицу вместе. Для целей нисходящего потока я хотел бы иметь как можно меньше «потраченного впустую» пространства в полученной оборванной матрице, следовательно, совпадение пространства.
До сих пор я использую жадный подход, обрабатывающий от самых больших целых чисел вниз и нахождение наибольшего целого числа, которое вписывается в текущее подмножество под пределом N. Как только наименьшее целое больше не вписывается в текущее подмножество, я продолжаю к следующему подмножеству так же, пока все номера не будут исчерпаны. Это почти наверняка не находит оптимального решения, но это лучшее, что я мог бы придумать быстро.
BONUS: Мое приложение фактически требует партий, где существует ограничение на количество подмножеств в каждой партии (M). Таким образом, чем больше задача состоит в нахождении наименьшее количество партий, где каждая партия содержит М подмножества и каждое подмножество суммы до менее чем Н.
Не могли бы вы просто подумать об этом как о проблеме ранца, когда вес каждого предмета является его значением, каждый элемент стоит 1 или дисперсия в текущем рюкзаке (некоторые эвристики для учета больших чисел в паре с меньшими) и емкость рюкзака равна N, и итеративно заполнять рюкзаки до тех пор, пока номера не останутся? – Aderis
Я просто признаю, что если у вас есть полные списки в ваших списках, допустим, что N равно 30, и у вас есть 3 списка, и у вас есть сумма 27, одна из 25 и одна из 10. Тогда у вас есть оптимальное решение, потому что нет возможности разделить 10 элементов на список 27 и 25, в которых не хватает только суммы 8, но вам нужно будет разделить вес 10. 10. –
Разве это не проблема с упаковкой? –