Задача: есть N*M предметов, каждый со своей массой. Нужно их разложить на N кучек по M предметов так, чтобы общая масса каждой кучки находилась в определённом диапазоне (видимо полезно будет, чтобы масса кучек стремилась к середине диапазона). Если не получается разложить так, чтобы все кучки попали в диапазон, то нужно максимизировать кол-во кучек.

Общее число предметов невелико, несколько десятков. Кол-во предметов в кучке также низко — от 10 до 15 (но всегда постоянно, т.е. кучки по кол-ву одинаковы).

Правильно понимаю, что смотреть нужно в сторону алгоритмов кластеризации? Или ошибаюсь? Тогда куда смотреть?

Здравствуйте, Кондраций, Вы писали:


К>Правильно понимаю, что смотреть нужно в сторону алгоритмов кластеризации?
Нет, кластеризация — это такой метод машинного обучения без учителя, тут он ни к чему.

К> Тогда куда смотреть?
В сторону multiple subset partition problem.

Ну и на самом деле важно, например, знать ещё границы допустимых интервалов. Если они достаточно велики, то и быстрый жадный алгоритм может давать приемлемое решение.

Здравствуйте, Кондраций, Вы писали:

К>Задача: есть N*M предметов, каждый со своей массой. Нужно их разложить на N кучек по M предметов так, чтобы общая масса каждой кучки находилась в определённом диапазоне (видимо полезно будет, чтобы масса кучек стремилась к середине диапазона). Если не получается разложить так, чтобы все кучки попали в диапазон, то нужно максимизировать кол-во кучек.

К>Общее число предметов невелико, несколько десятков. Кол-во предметов в кучке также низко — от 10 до 15 (но всегда постоянно, т.е. кучки по кол-ву одинаковы).

К>Правильно понимаю, что смотреть нужно в сторону алгоритмов кластеризации? Или ошибаюсь? Тогда куда смотреть?

Пока шёл домой, сообразил, что не выложил всю важную информацию.
В общем, предметы — это изделия, масса которых должна быть вполне определённой +/- допуск (а не что-то где-то найденное). Т.е. их стараются делать так, чтобы кучки сложились. А раз так, то достаточно будет отсортировать их по массе, а затем отбирать в кучки с начала и конца отсортированной коллекции (тяжёлые будут компенсироваться легкими). Раз так, то проблема не стоит выеденного яйца.

Всем спасибо!

Здравствуйте, Кондраций, Вы писали:

К>Правильно понимаю, что смотреть нужно в сторону алгоритмов кластеризации? Или ошибаюсь? Тогда куда смотреть?

Нет, это частный случай задачи об упаковке рюкзака.

Здравствуйте, Miroff, Вы писали:

M>Здравствуйте, Кондраций, Вы писали:

К>>Правильно понимаю, что смотреть нужно в сторону алгоритмов кластеризации? Или ошибаюсь? Тогда куда смотреть?

M>Нет, это частный случай задачи об упаковке рюкзака.
Там буквы по ссылке странные В школе такие видел Буду стараться понять

Здравствуйте, Miroff, Вы писали:

M>Здравствуйте, Кондраций, Вы писали:

К>>Правильно понимаю, что смотреть нужно в сторону алгоритмов кластеризации? Или ошибаюсь? Тогда куда смотреть?

M>Нет, это частный случай задачи об упаковке рюкзака.
Не, по моему ничего общего (кроме того, что в обоих случаях масса упоминается). Рюкзаков много, максимизировать ничего не нужно (понятно, что целевую функцию придумать можно любую, в т.ч. и для максимизации), просто равномерно разложить.

Здравствуйте, Кондраций, Вы писали:

M>>Нет, это частный случай задачи об упаковке рюкзака.
К>Не, по моему ничего общего (кроме того, что в обоих случаях масса упоминается). Рюкзаков много, максимизировать ничего не нужно (понятно, что целевую функцию придумать можно любую, в т.ч. и для максимизации), просто равномерно разложить.

Ну все NP-полные задачи похожи друг на друга. Твоя задача — это обобщение 3-partition problem, которое является обобщением partition problem, которое сводится к subset sum problem, что в свою очередь является частным случаем задачи об упаковке рюкзака. Как видишь, ничего сложного :) С другой стороны, можно было бы сразу на 3-partition остановится, не уходя так далеко.