Максимальное количество комбинаций суммы целых чисел
В принципе, учитывая отсортированный список положительных ненулевых чисел, скажем, {1, 4, 5}, измените одно число в списке, чтобы максимально использовать различные комбинации. Вышеприведенное дает
1, 4, 5, 6, 9, 10, то есть шесть комбинаций. Если бы мы изменили 4 на 2, значит, у нас есть {1, 2, 5}, мы получим 1, 2, 3, 5, 6, 7, 8, то есть семь комбинаций.
Мне нужно найти число x, чтобы добавить к одному номеру списка, чтобы максимизировать количество комбинаций. x должно быть наименьшим значением abslout, мы можем как добавить, так и вычесть.
Я сделал это с использованием грубой силы путем перечисления, которое выполняется во много раз экспоненциальное время. Таким образом, это не представляется возможным для больших проблем. Теперь мне нужно сделать это быстро.
Просто проверка количества комбинаций - это экспоненциальное время? И я должен найти точное оптимальное решение.
Какими будут ключевые слова для решения этой проблемы? Я попытался найти повторение, поэтому я мог бы использовать динамическое программирование и какую-то ветвь и ограничивать ее, но это бесполезно.
Я рассмотрел такие проблемы, как режущий станок, подмножество sum и множество других комбинаторных задач оптимизации, чтобы увидеть, могу ли я найти некоторые идеи. Но я этого не понимаю. Простое подтверждение решения - это экспоненциальное время.
Ответы
Ответ 1
Это просто удар по нему, я не написал кода или даже не выработал никаких доказательств.
Поскольку вы ограничены изменением только одного значения, я бы подумал, что самый простой способ устранения комбинаций (который, как я знаю, вы не пытаетесь сделать, но выслушайте меня) состоит в том, чтобы сделать два числа, число в списке. Итак, в вашем примере 1 4 5, потому что 1 + 4 = 5 вы проигрываете на комбинациях. Поэтому я бы сделал запрос набора чисел, для которых число пар приводит к другому члену набора. Это O(n^2 lg n), поскольку вы сравниваете каждое число с любым другим числом и при этом также выполняете поиск (отсортированный) список чисел, чтобы найти, существует ли он.
Ваш кандидат - это тот, который имеет наибольшее количество "столкновений". Руки вниз, сделав наивысший угол столкновения с номером нулевого столкновения, вы получите максимальное увеличение конечных результатов. Оттуда просто нужно найти, какое число добавить/вычесть на него, чтобы сделать его числом без столкновений. Я не разработал правильный способ сделать это, но я подозреваю, что это можно сделать с динамическим программированием в полиномиальное время.
Есть еще одна серьезная проблема, в которой у вас есть связи. Я думаю, что это в худшем случае добавит дополнительную *n к вашей сложности, так как вы будете иметь не более n связей для одновременного поиска. Предположим, что вы можете вычислить указанную выше проблему в n^p время, когда p - некоторый постоянный многочлен, тогда вся проблема должна быть решена в n^(p+1) времени.
Это, безусловно, сволочь проблемы, и я надеюсь, что это могло пролить свет на нее. Через два месяца кто-то должен нанести удар, верно?:)
Ответ 2
Предположим, что вопрос был: при любом значении n, какие n положительных целых чисел дают максимальное количество комбинаций. Ответ на этот вопрос: 2 ^ 0, 2 ^ 1, 2 ^ 2,... 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} и имеет одну меньшую комбинацию. Это совпадение?
Если эти наблюдения останутся на рассмотрении, я подозреваю, что их не будет слишком сложно доказать. Даже если вы не можете их доказать, они могут дать вам алгоритм, который работает.
