Пусть сумма всех элементов равна full_sum, а длина массива 2k.
Предлагаю организовать банальный перебор: выберем k индексов из 2k, посчитаем сумму соответствующих элементов. Будем искать максимальную сумму, которая не превосходит full_sum/2. При этом сумма невыбранных элементов будет не меньше full_sum/2, и будет отличаться от суммы выбранных элементов на минимально возможную величину.
Этот алгоритм работает быстро только для относительно небольших значений k. если нужно что-то быстрее, то придется придумывать что-то дополнительно.
Код (Python 3):
from random import randint
from itertools import combinations
k = 10
a = [randint(1, 100) for _ in range(2 * k)]
print(*a)
full_sum = sum(a)
half_sum = full_sum // 2
max_sum = -1
answer = None
for seq in combinations(range(2 * k), k):
s = sum(map(lambda ind: a[ind], seq))
if s <= half_sum and s > max_sum:
max_sum, answer = s, seq
if s == half_sum:
break
left = [a[i] for i in answer]
right = [el for i, el in enumerate(a) if i not in answer]
a = left + right
print(*a)
Пример вывода:
50 39 19 63 16 4 82 45 63 33 6 57 39 16 38 4 66 56 87 84
50 39 19 63 16 4 82 57 16 87 45 63 33 6 39 38 4 66 56 84
1. Растровая
2. Векторная
3. 3D графика
5. Фрактальная
Объяснение:
1. Видим обычное изображение, снятое на камеру. Сплошное, образованное набором пикселей. Растровая графика
2. Видим изображение, образованное набором геометрических примитив (фигур). Выглядит как логотип. Векторная графика
3. Видим изображение трехмерных объектов. Скорее всего использовалась 3D графика для описания объектов и источников света, а затем был произведен рендер на плоскость изображения.
4. Видим рекурсивный узор, построенный с фрактала. Фрактальная графика
