Я думаю, что это можно решить в O(N log(N)).
Любая перестановка может быть получена путем замены пар смежных элементов; Вот почему, например, работает сортировка пузырьков. Итак, давайте посмотрим на эффект подкачки записей (A[i], B[i]) и (A[i+1], B[i+1]). Мы хотим выяснить, в каких случаях это хорошая идея сделать этот обмен. Это влияет только на i-й и i+1-й термины, остальные остаются неизменными. Кроме того, как до, так и после свопа оба условия имеют коэффициент B[1]*B[2]*...*B[i-1], который мы можем назвать C. C - положительное число.
Перед заменой, мы имеем дело с C*A[i] + C*B[i]*A[i+1], а затем - C*A[i+1] + C*B[i+1]*A[i]. Это улучшение, если разница между ними положительна:
C*(A[i] + B[i]*A[i+1] - A[i+1] - B[i+1]*A[i]) > 0
С C положителен, мы можем игнорировать этот фактор и смотреть только на A с и B с. Мы получаем
A[i] - B[i+1]*A[i] > A[i+1] - B[i]*A[i+1]
или, что эквивалентно
(1 - B[i+1])*A[i] > (1 - B[i])*A[i+1]
Оба эти выражения неотрицательны; если один из B[i] или B[i+1] равен единице, то термин, содержащий «один минус этой переменной», равен нулю (поэтому мы должны поменять местами, если B[i] является одним, но не если B[i+1] является одним); если обе переменные равны единице, то оба слагаемых равны нулю. Предположим теперь, что ни один не равен единице; то мы можем переписать дальше, чтобы получить
A[i]/(1 - B[i]) > A[i+1]/(1 - B[i+1])
Таким образом, мы должны вычислить это выражение D[i] := A[i]/(1 - B[i]) для обоих членов и поменять их местами, если левый один больше, чем правая. Мы можем распространить это на случай, когда один или оба B s являются едиными, определяя в этом случае D[i].
ОК, давайте вернемся - что мы нашли? Если есть пара i, i+1, где D[i] > D[i+1], мы должны обменять эти две записи.Это означает, что единственный случай, когда мы не можем улучшить результат путем замены, - это когда мы изменили порядок пар, чтобы значения D[i] были в порядке возрастания - то есть все случаи с B[i] = 1 приходят последними (напомним, что это соответствует D[i] бесконечно велико) и в остальном в порядке возрастания D[i]. Мы можем добиться этого путем сортировки по значению D[i]. Быстрый анализ наших шагов выше показывает, что порядок пар с равным D[i] значением не влияет на конечное значение.
Вычисление всех значений D[i] может быть выполнено за один проход с линейным временем. Сортировка может быть выполнена с помощью алгоритма O(N log(N)) (нам нужно, чтобы элементы подкачки соседних элементов были только аргументом/доказательством, чтобы показать, что это оптимальное решение, а не как часть реализации).
Без потери вообще допустим An> = An-1 .... > = A2> = A1, если Bi имеют одинаковую последовательность, тогда ответ, очевидно, A1 + B1 A2 + B1 B2 A3 + .... , В случае, если все не так просто, и Bi не имеют такой же последовательности, как Ai, тогда я думаю, что нет способа найти лучший ответ за полиномиальное время, возможно, вы могли бы найти примерно лучший ответ в полиномиальном время с жадным или ДП, но вы не можете найти точный наименьший ответ за полиномиальное время. – Lrrr
@AliAmiri no, если An> An-1 это не означает, что Bn> Bn-1, и я в основном уверен, что для этой проблемы существует многочленное решение, потому что я должен сделать это для довольно большого количества данных , –
В настоящее время я нахожусь на работе, а также я не помню подход к сопоставлению NP-проблем очень хорошо, но я думаю, что можно доказать, что это NP, но я думаю, что есть много изменений, которые вы могли бы сделать и сократить время работы. Но я надеюсь, что ошибаюсь, и это не NP :) – Lrrr