Рассфассовка шаров по коробкам

Приветствую участников форума!
На входе имеем массив из чисел:
in = [11, 8, 2, 5, 22, 2, 4, 4, 9, 12, 16, 13, 3]

Нужно разбить этот массив на массивы, чтобы каждый содержал элементы, в сумме которые не выходят за границы нижнего и верхнего пределов(к примеру: 25-30), а оставшиеся элементы отбросить.

Если приводить аналогию с реальным миром то: Имеется куча шаров разного объема, из необходимо рассфасовать по коробкам определенного размера, а оставшиеся шары выкинуть.

На выходе:
out = [
[11, 8, 4, 4], //= 27
[22, 2, 3], //= 27
[12, 16], //= 28
[13, 9, 5], //= 27
[2] //= остаток, отброс
]


У меня уже есть эта функция, и она работает не так ка нужно, взять хотя-бы эту двойку в остатке, ее можно положить в любой из массивов и он не выйдет за пределы верхней границы.

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

0

Это задача на разновидности диофантовых уравнений и неравенств, которые в общем случае аналитически не решаются.

0

Мне кажется эта задача больше похожа на https://ru.wikipedia.org/wiki/... 0%ED%F6%E5.
Первым делом - нужно найти кол-во коробок для рассфасовки:
сумма всех элементов массива in = [11, 8, 2, 5, 22, 2, 4, 4, 9, 12, 16, 13, 3] равна 111,
это число поделить на нижнюю границу предела - 25, равно 4 (при целочисленном делении).
И затем мне нужно как-то рассфасовать причем это сделать максимально сбалансированно, так сказать утрести.

Вот здесь похожая проблема, якобы задача сводиться к нахождению четности элементов.

0

Сообщение от legkoe_poxmelye Первым делом - нужно найти кол-во коробок для рассфасовки: сумма всех элементов массива in = [11, 8, 2, 5, 22, 2, 4, 4, 9, 12, 16, 13, 3] равна 111, это число поделить на нижнюю границу предела - 25, равно 4 (при целочисленном делении).

Результат зависит от верхней границы, а Вы её не используете.
(Например, если верхняя граница 200, то достаточно одной коробки).

Добавлено через 8 минут

Сообщение от legkoe_poxmelye И затем мне нужно как-то рассфасовать причем это сделать максимально сбалансированно, так сказать утрести.

Если устроит приближенное решение, то можно использовать жадный алгоритм: отсортировать шары и класть в максимально заполненный, в который можно.

[11, 8, 2, 5, 22, 2, 4, 4, 9, 12, 16, 13, 3]
[22, 16, 13, 12, 11, 9, 8, 5, 4, 4, 3, 2, 2]
[22, 8], [16, 13], [12, 11, 5, 2], [9, 4, 4, 3, 2]

1

Shamil1,
Да действительно, если честно то я уже стал брать во внимание только максимальную границу для решения задачи.
Еще пришла идея, такая:
1) Отсортировать исходный массив
in = [22, 16, 13, 12, 11, 9, 8, 5, 4, 4, 3, 2, 2]
2) Вложить последовательно в каждую коробку максимальные элементы
in = [11, 9, 8, 5, 4, 4, 3, 2, 2]
out = [
[22],
[16],
[13],
[12]
]
3) Затем в цикле добавлять следующий элемент массива in в массив out, туда, где сумма элементов минимальная:
//->iter(1)
in = [9, 8, 5, 4, 4, 3, 2, 2]
out = [
[22],
[16],
[13],
[12, 11]
]
//->iter(2)
in = [8, 5, 4, 4, 3, 2, 2]
out = [
[22],
[16],
[13, 9],
[12, 11]
]
//->iter(3)
in = [5, 4, 4, 3, 2, 2]
out = [
[22],
[16, 8],
[13, 9],
[12, 11]
]
//->iter(4)
in = [4, 4, 3, 2, 2]
out = [
[22, 5],
[16, 8],
[13, 9],
[12, 11]
]
//->iter(5)
in = [4, 3, 2, 2]
out = [
[22, 5],
[16, 8],
[13, 9, 4],
[12, 11]
]
//->iter(5)
in = [3, 2, 2]
out = [
[22, 5],
[16, 8],
[13, 9, 4],
[12, 11, 4]
]
//->iter(6)
in = [2, 2]
out = [
[22, 5],
[16, 8, 3],
[13, 9, 4],
[12, 11, 4]
]
//->iter(7)
in = [2]
out = [
[22, 5],
[16, 8, 3],
[13, 9, 4, 2],
[12, 11, 4]
]
//->iter(8)
in = []
out = [
[22, 5, 2], // 29
[16, 8, 3], // 27
[13, 9, 4, 2], // 28
[12, 11, 4] // 27
]
Решение не идеальное но на замену того что у меня уже есть - достаточно, к тому же время здесь линейное

Добавлено через 2 минуты
А ну вот, похоже мы говорим об одном и том же, об жадном алгоритме.

0

Сообщение от legkoe_poxmelye А ну вот, похоже мы говорим об одном и том же, об жадном алгоритме.

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

0