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

Question

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

Проблема:

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

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])

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

Answer 1

Если предположить, что записи 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.

Answer 2

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

Из-за NP-Hardness этой проблемы:

Имеются ли k и массив B, есть липодмножество размера k из B, сумма которого равна нулю.

В этом случае A становится несущественным.

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