Алгоритм категоризации значений

Question

Какой будет лучший алгоритм для решения этой проблемы? Я потратил пару часов на эту проблему. Но не мог разобраться.

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

Критерии для разделения ожерелий

1. Разница в количестве жемчужин между двумя наборами жемчужин не должна превышать 10% от количества жемчужин в оригинальном ожерелье или 3, в зависимости от того, что больше.

2. Разница между количеством жемчужин в 2 ожерельях должна быть минимальной.

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

4.Два ожерелья должны иметь среднюю яркость, превышающую исходную, и разница между средней яркостью двух частей минимальна.

5. Средняя яркость каждого куска должна быть больше или равна исходному.

Answer 1

Эту проблему довольно сложно решить эффективно (где-то в NP).

Скажем, у вас был набор, который в среднем составил X. То есть X = (x1 + x2 + ... + xn) / n.

Предположим, вы разбили его на наборы, которые в среднем составляют S и T с s и t элементами в каждом наборе соответственно.

Вы можете математически доказать, что если одно из средних значений S или T больше X, то другое из двух должно быть меньше X.

Следовательно, два комплекта должны иметь одинаковую яркость, потому что только так ваши условия могут быть выполнены.

Зная это, вы в конечном итоге сталкиваетесь с проблемой sumset sum - вы хотите найти подмножество, равное половине всей суммы всего набора. Это проблема, которая, как известно, сложная. (Это было классифицировано как NP. И хорошо, это не совсем то же самое, что и проблема суммы подмножеств, но если вычесть среднее из полного набора из каждого из значений яркости, решение проблемы суммы подмножеств даст вам ответ. Обратитесь, чтобы увидеть, как вы можете решить проблему суммы подмножеств из вашей задачи.)

Следовательно, нет быстрого способа сделать это - только приближения или экспоненциальное время выполнения ... Однако, возможно, это поможет. Он упоминает лучшее время работы, если ваши веса (в вашем случае, уровни яркости) ограничены.