Максимизация количества комбинаций суммы целых

Question

Обычно, учитывая отсортированный список положительных ненулевых чисел, скажем, {1, 4, 5}, измените одно число в списке, чтобы максимизировать возможные комбинации.Выше приведены 1, 4, 5, 6, 9, 10, то есть шесть комбинаций.Если бы мы изменили 4 на 2, чтобы у нас было {1, 2, 5}, мы бы получили 1, 2, 3, 5, 6, 7, 8, то есть семь комбинаций.

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

Я сделал это, используя грубую силу путем перечисления, которое выполняется во много раз экспоненциально.Так что это не выполнимо для больших проблем.Теперь мне нужно сделать это быстро.

Просто проверка количества комбинаций - это экспоненциальное время?И я должен найти точное оптимальное решение.

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

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

Answer 1

Это всего лишь удар, я не написал ни одного кода или даже разработал какие-либо доказательства для него.

Поскольку вы ограничены изменением только одного значения, я считаю, что самый простой способ исключить комбинаций (что, я знаю, вы не пытаетесь сделать, но выслушайте меня), означает добавление двух чисел к другому числу в списке.Так что в вашем примере 1 4 5, потому что 1 + 4 = 5 вы проигрываете там комбинации.Поэтому я бы сделал запрос набора чисел, для каких пар чисел получился другой член набора.Это O(n^2 lg n), так как вы сравниваете каждое число с любым другим числом, и при этом также ищите (отсортированный) список чисел, чтобы узнать, существует оно или нет.количество «столкновений».Руки вниз, сделав наибольшее число склонных к столкновениям числом нулевых столкновений, вы получите максимальное увеличение конечных результатов.Оттуда, это просто вопрос того, какое число добавить / вычесть к нему, чтобы сделать его числом без столкновений.Я не разработал правильный способ сделать это, но я подозреваю, что это можно сделать с помощью динамического программирования за полиномиальное время.

Существует еще одна серьезная проблема, в которой у вас есть связи.Я думаю, что в худшем случае к вашей сложности добавится дополнительный *n, поскольку у вас будет максимум n связей для одновременного поиска.Таким образом, предполагая, что вы можете вычислить вышеупомянутую задачу за n^p время, когда p - некоторый постоянный полином, тогда вся проблема должна быть решаема за n^(p+1) время.Я надеюсь, что это смогло пролить свет на это.Через два месяца кто-то должен нанести удар, верно?:)

Answer 2

Предположим, что вопрос был: для любого значения n, какие n натуральных чисел дают максимальное количество комбинаций. Ответ на этот вопрос: 2 ^ 0, 2 ^ 1, 2 ^ 2, ... 2 ^ (n-1).

Доказательство простое, потому что:

• с этим набором вы можете создать каждое целое число от 2 ^ 0 до (2 ^ n) -1.

• этот набор сумм равен (2 ^ n) -1.

Рассмотрим {1, 2, 4}. Комбинации: 1, 2, 1 + 2, 4, 1 + 4, 2 + 4 и 1 + 2 + 4. 1 + 2 + 4 = 7.

Разумно предположить, что для любого набора вы максимизируете количество комбинаций, делая набор максимально похожим на 2 ^ 0, 2 ^ 1, ...

Я не уверен, что означает "настолько похожий, насколько возможно". Однако {1, 2, 5} ближе к {1, 2, 4}, чем {1, 4, 5}. Это верно для других наборов, которые вы исследовали грубой силой?

Я замечаю, что {1, 2, 5} один от {1, 2, 4} и имеет на одну комбинацию меньше. Это совпадение?

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