Алгоритм максимизации произведения сил

Question

Учитывая два массива целых чисел, B и A, как мы можем переставить их элементы так, чтобы ∏ A [i] ^{B [i]} для всех i было максимизировано?

Answer 1

Предполагая, что неотрицательно, кажется, что вы должны просто отсортировать их в порядке увеличения или уменьшения (но в том же порядке).

Поскольку все умножено, вы получите A [0] * A [0] * ... * A [0] * A [1] * .. * A [1] *... и т. д.

С B [0] числом A [0] и B [1] числом A [1], поэтому, если вы предполагаете, что A [0] является наибольшим числомвам нужно большинство из них, поэтому у вас должно быть самое большое значение B в B [0], а затем вы хотите второе наибольшее значение в B [1] и т. д.

Если вы можете иметь отрицательные числа вA, но не B, тогда это все равно дает наибольшее абсолютное значение, но знак может быть отрицательным.

Answer 2

Предполагая, что массив имеет положительные целые числа,

Если вы берете журнал продукта:

Становится Sum B[i]* log A[i]

Теперь это может быть максимизировано, если оба расположены в порядке возрастания из-за неравенства перестановок (см. Здесь: http://en.wikipedia.org/wiki/Rearrangement_inequality) и log - возрастающая функция.

Итак, сортируйте A по возрастанию, сортируйте B по возрастанию, и все готово.

Answer 3

Если массивы содержат неотрицательные числа, вы просто сортируете и A, и B в порядке убывания. Чтобы увидеть, что это дает максимальный продукт, рассмотрим, как только A и B отсортированы в этом порядке, вы можете попробовать поменять местами два элемента A, скажем, A [i] и A [j] s.t. я

              B[j]      B[i]
          A[i]      A[j]
          ------------------
              B[i]      B[j]
          A[i]      A[j]

т.е. A [i] ^{B [j] -B [i]} A [j] ^{B [i] -B [j]} , что равно (A [i] / A [j ]) ^{(B [j] -B [i])} где показатель степени равен нулю или отрицателен, поскольку B [i] & geq; В [J]. По предположению A [i] & geq; A [j], так что A [i] / A [j] & geq; 1. Следовательно, отношение равно 1 или меньше, поскольку показатель степени равен 0 или отрицателен. Это показывает, что новый продукт имеет меньшую стоимость, чем старый. Примечание: это просто иллюстрация, а не формальное доказательство, потому что она рассматривает только обмен двух элементов.