Как выбрать элементы из двух массивов, чтобы их сумма была минимальной? - PullRequest
Новая
       41

Как выбрать элементы из двух массивов, чтобы их сумма была минимальной?

0 голосов
/ 03 февраля 2019

У меня есть два массива одинаковой длины, заполненные целыми числами (могут быть положительными или отрицательными, но никогда не равными 0).Для каждого индекса я могу выбрать либо элемент массива1, либо массив2, и абсолютное значение суммы таких элементов должно быть минимальным.

Например: 

a1 = [2, 2, 1]
a2 = [-3, -3, -4]

Правильный ответ будетбыть выбранным так: 

At index 0 : -3 from a2
At index 1 : 2 from a1
At index 2 : 1 from a1

Таким образом, итоговая сумма будет равна 0.

Ответы [ 3 ]

0 голосов
/ 03 февраля 2019 
import itertools as iter
a = [a1, a2]
p = len(a1)
idx_to_pick = min(iter.product(*([[0, 1]]*p)), 
                  key=lambda b: abs(sum([a[i][j] for i, j in zip(b, range(p))])))

этот код предлагает выбрать a1[0] + a1[1] + a2[2] = 2 + 2 + (-4), отличается от выбора ОП, но также является правильным.

Обновить для каждого последующего вопроса ОП в комментарии к этому ответу: 

import itertools as iter
a1 = [2, 2, 1]
a2 = [-3, -3, -4]
a = [a1, a2]
p = len(a1)


def obj_func(b):
    arr = [a[i][j] for i, j in zip(b, range(p))]
    return sum([x for x in arr if x > 0]) + abs(sum(arr))


idx_to_pick = min(iter.product(*([[0, 1]]*p)), key=obj_func)

С новой целевой функцией все еще существует множество решений.Это может быть (-3, 2, 1) или (2, -3, 1)

0 голосов
/ 03 февраля 2019

Вот решение для динамического программирования, которое находит минимальное значение для pos + abs(neg + pos) (согласно обновлению OP) и печатает одно из возможных решений.Нам нужно сохранить как общую сумму, так и сумму натуральных чисел как состояние dp, чтобы найти минимум.Я не уверен, сможем ли мы решить это без измерения pos.Сложность времени составляет O(#elements * (sum of absolute values of elements)^2).Конечно, если отдельные числа очень велики, это неосуществимое решение.В этом случае подход грубой силы будет работать, когда число элементов равно ~20. 

a1 = [2, 1, 1, -1] 
a2 = [-1, -2, -2, -4]
memo = {}   # to store dp state
nxt = {}    # for reconstructing path

def foo(a1, a2, index, total, pos):
    if index == len(a1):
        return pos + abs(total)
    if (index, total, pos) in memo:
        return memo[(index, total, pos)]

    # take from first array
    if a1[index] > 0:
        r1 = foo(a1, a2, index+1, total + a1[index], pos+a1[index])
    else:
        r1 = foo(a1, a2, index+1, total + a1[index], pos)

    # take from second array
    if a2[index] > 0:
        r2 = foo(a1, a2, index+1, total + a2[index], pos+a2[index])
    else:
        r2 = foo(a1, a2, index+1, total + a2[index], pos)

    # save path taken at this step
    if r1 < r2:
        nxt[index] = 0
    else:
        nxt[index] = 1

    memo[index, total, pos] = min(r1, r2)
    return min(r1, r2)

print('minimum sum:', foo(a1, a2, 0, 0, 0))   # minimum sum: 2
# path reconstruction
path = []
node = 0
while node < len(a1):
    path.append(nxt[node])
    node += 1
print('path:', path)   # path: [1, 0, 0, 0]
0 голосов
/ 03 февраля 2019

Сначала упростим вопрос:

  • Создать массив b, где b[i] = a1[i] - a2[i].
  • sumA1 = сумма каждого элемента в a1.

Тогда возникает проблема:

Найдите подмассив из b, пометьте как c, отметьте его сумму как sumC, которая должна быть ближайшей к sumA1.

Или вы также можете сказать, что он должен иметь минимальное значение Math.abs(sumC - sumA1).

Кстати, если c пусто, это также верно, что означает выбор всех индексов из a1.

Тогда этот вопрос похож на этот: По заданному входному массиву найдите все подмассивы с заданной суммой K

Или обратитесь к этой статье:

И, чтобы вернуться к вопросу OP:

  • Все индексы, выбранные в b, предназначены для a2.
  • Любые индексы, не выбранные в b, относятся к a1.
...