Максимальная сумма подмножества с двумя массивами

Я даже не уверен, что это можно сделать за полиномиальное время.

Проблема:

Даны два массива действительных чисел,

A = (a[1], a[2], ..., a[n]), 
B = (b[1], b[2], ..., b[n]),  (b[j] > 0, j = 1, 2, ..., n)

и число k, найти подмножество A' числа A (A' = (a[i(1)], a[i(2)], ..., a[i(k)])), которое содержит ровно k элементов, такое, что (sum a[i(j)])/(sum b[i(j)]) максимально, где
j = 1, 2, ..., k.

Например, если результатом является k == 3, а {a[1], a[5], a[7]}, то

(a[1] + a[5] + a[7])/(b[1] + b[5] + b[7])

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


arrays algorithm math subset-sum
person Geni    schedule 11.11.2011    source источник
comment
Я предполагаю, что это NP-Hard с вероятностью 99,99%, но могу я спросить вас, где вы видите эту проблему? В целом, это действительно хороший вопрос.   -  person Saeed Amiri    schedule 12.11.2011
comment
Спасибо за ответ. Я свел реальную проблему балансировки нагрузки к этой абстрактной версии. Я потратил больше двух дней на эту проблему. Теперь у меня также есть ощущение, что это NP-сложно.   -  person Geni    schedule 12.11.2011
comment
Есть n выбрать k возможных соотношений, так что это устанавливает верхнюю границу сложности. Я рассматривал способ выбрать наибольшее отношение a[i]/b[i] для начала, а затем выбрать индекс, который делает случай k=2 максимально большим. Таким образом, вы должны сравнить n-1 отношения на этом шаге. Затем продолжите, выбрав третий индекс. Доказать, что это всегда будет давать наилучшее соотношение после того, как вы выбрали k индексов, может быть сложно (или это может быть не так!), но попытка доказать может дать некоторое представление.   -  person JohnPS    schedule 12.11.2011
comment
Привет Джон, большое спасибо за ваш ответ. Я пытался вчера доказать правильность вашего алгоритма, но в итоге получил контрпример. проверьте это A = [10, 2, 1, 0,2], B = [7, 3, 2, 1,34] и k = 3.   -  person Geni    schedule 12.11.2011
comment
Могут ли a[i] и b[i] быть нулевыми или отрицательными?   -  person Anonym Mus    schedule 12.11.2011
comment
@Geni - я подозревал такой контрпример.   -  person JohnPS    schedule 12.11.2011

Ответы (2)


arrow_upward
3
arrow_downward

Предполагая, что записи B положительны (звучит так, как будто этот особый случай может быть вам полезен), существует алгоритм O(n^2 log n).

Давайте сначала решим задачу определения для конкретного t, существует ли такое решение, что

(sum a[i(j)])/(sum b[i(j)]) >= t.

Очищая знаменатель, это условие эквивалентно

sum (a[i(j)] - t*b[i(j)]) >= 0.

Все, что нам нужно сделать, это выбрать k наибольших значений a[i(j)] - t*b[i(j)].

Теперь, чтобы решить задачу, когда t неизвестно, воспользуемся кинетическим алгоритмом. Думайте о t как о переменной времени; нас интересует эволюция одномерной физической системы с n частицами, имеющими начальные положения A и скорости -B. Каждая частица пересекает другую частицу не более одного раза, поэтому количество событий равно O(n^2). Между пересечениями оптимум sum (a[i(j)] - t*b[i(j)]) изменяется линейно, потому что то же самое подмножество k является оптимальным.

person Per    schedule 12.11.2011
comment
Я подозреваю, что существует алгоритм O(n^2), который использует расположение линий и вычислительно-геометрический механизм, разработанный для их обработки. - person Per; 12.11.2011
comment
+1 Отличный ответ. Я никогда не видел ничего подобного. Мне любопытно, можно ли применить этот метод к более широкому классу проблем и как называется этот тип решения... или вы взяли это из воздуха? - person JohnPS; 13.11.2011
comment
@JohnPS Кинетические алгоритмы — это метод проектирования, который предпочитают вычислительные геометры. Они применимы, когда у вас есть непрерывный параметр (интерпретируемый как время) и физическая система, которая хорошо изменяется, за исключением конечного числа раз. - person Per; 13.11.2011

arrow_upward
2
arrow_downward

Если B может содержать отрицательные числа, то это NP-Hard.

Из-за NP-трудности этой проблемы:

Учитывая k и массив B, существует ли подмножество размера k из B, которое в сумме равно нулю.

В этом случае буква А становится несущественной.

Конечно, из вашего комментария кажется, что B должен содержать положительные числа.

person user127.0.0.1    schedule 12.11.2011
comment
Привет! Спасибо за ответ. Извините, я забыл упомянуть, что B содержит только положительные числа. - person Geni; 12.11.2011