Найдите минимальное и максимальное значения: один член представляет собой сумму nCr-комбинации массива, а другой - сумму остальных элементов.

Question

Скажем, вам дан массив целых чисел со знаком, называемый NUMBERS длиной r. Скажем, NUMBERS равно

1, 2, 3, 4, 5

, где r = 5.

Вы хотите сформировать сумму X любого n элементов набора NUMBERS и умножьте это на сумму Y оставшихся m элементов для любого заданного n. Таким образом, длина массива NUMBERS составляет (n + m) слов в памяти.

Например, с n = 2 можно получить возможную комбинацию для X, являющуюся суммой произвольных n = 2 элементов 1 + 4 и, следовательно, суммой Y оставшихся m = 3 элементов 2 + 3 + 5. Затем вы умножаете обе суммы, чтобы получить: X * Y = 5 * 10 = 50.

Другой способ выразить это будет:
Учитывая (n + m)целые числа со знаком, найдите минимальный и максимальный результат алгебраического выражения в форме:

(x1 +x2 +x3 +...+xn)*(y1 +y2 +...+ym)

для фиксированного значения n.

Это включает в себя поиск всех nCr-комбинаций набора NUMBERS, где задано n, и затем нахождение суммы X для каждой комбинации, затем вычисление суммы Y оставшихся элементов, не использованных для суммы X. Затем умножение обоих,Используя формулу комбинаторики nCr, вы можете получить количество возможных комбинаций суммы X и соответствующей суммы Y, а затем перебрать каждое умножение, чтобы увидеть, какой из них даст наименьший или наибольший результат.

Я не уверенкак поступить, тем более что рекурсия и вложенные циклы находятся за рамками этого первого проекта.

Answer 1

Я добавил комментарий, но удалил его, поскольку понял, что допустил ошибку. Тем не менее, я сделал еще несколько экспериментов. Я добавляю это как ответ, чтобы иметь возможность использовать форматирование.

Я не проводил обширных экспериментов, поэтому я не гарантирую, что это верно для всех ситуаций, но тесты, которые я сделал, показывают, что, если вы сортируетенабор чисел, то этот факт, кажется, справедливо (когда n <= m): </p>

minval = (sum of first item(s) * sum of [remaining] last item(s))
maxval = (sum of first item(s) + last item(s)) * (sum of [remaining] middle item(s))

Например, если вы получите набор A {4, 8, 1, 6, 3} => A {1, 3, 4, 6, 8} и n = 2, тогда:

minval = (A[0] + A[1]) * (A[2] + A[3] + A[4]) = 72
maxval = (A[0] + A[4]) * (A[1] + A[2] + A[3]) = 135

Для своих экспериментов я использовал заданные длины от len = 4 до len = 8. Эти эксперименты показывают, чтовыше, кажется, справедливо все время для этих установленных длин, и с изменениями n от n = 2 до n = (set.length-2) (для n = 1 (и n = (set.length-1))ответ очевиден). Для set.length = 3, кажется, немного отличается, но непротиворечиво каждый раз, когда с этими комбинациями дают минимальное и максимальное значения.

Так как это верно для заданных длин от 4 до 8, я предполагаю, что это имеет место для заданных длинтакже больше, чем 8.

Заданная длина 3 является своего рода «крайними случаями», но все же непротиворечива, если отсортирована по (или это не непосредственно крайний случай, но факт, что n> m):

minval = A[1] * (A[2]) * A[3]
maxval = (A[1] + A[2]) * A[3]

Задать длины 1 и 2 (если они существуют) - простые случаи.

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

РЕДАКТИРОВАТЬ: После или до сортировки, вы можете рассчитать сумму набора. Тогда вам нужно только сделать:

x1 = (A[0] + A[1])
x2 = (A[0] + A[4])
minval = x1 * (totalsum - x1) = 72
maxval = x2 * (totalsum - x2) = 135

EDIT2: после дальнейших экспериментов, похоже, что вышеприведенное не выполняется во всех случаях, как описано выше, но есть образец, который я уверен, что вы можетевоспользоваться.