Объедините ценности, чтобы создать букет из 100

Question

Предположим, у меня есть один массив, имеющий значения:

array(20,40,30,15,60,50,10)

Теперь я хочу создать группу из 100 или около ста. И создать отдельный раунд для каждого набора из 100(или около 100).

Сказать

Case 1:
Round 1: array(60,30,10) // 100 or near to 100
Round 2: array(40,50)    // 100 or near to 100
Round 3: array(15,20)    // 100 or near to 100 or remaining

Case 2:
Round 1: array(60,40)    // 100 or near to 100
Round 2: array(50,20,30) // 100 or near to 100
Round 3: array(15,10)    // 100 or near to 100 or remaining

Так как же мне этого добиться?

Есть ли какой-нибудь алгоритм относительно этого, который я могу изучить?

Answer 1

Вы описываете проблему бинпэкинга, которая является NP-Complete, поэтому нет никакого известного полиномиального решения для ее решения.

Вы можете попробовать экспоненциальный подход (проверить все возможности), если вам нужно точное. Если вы хотите "достаточно близко", вы можете найти в литературе какой-нибудь алгоритм приближения или использовать какое-то эвристическое решение для поиска из поля ИИ, такое как Genetic Algorithm или Hill Climbing.