Определение максимальной суммы элементов при минимальной разнице сумм максимальных и минимальных подсписков

Question

нужно выбрать подсписки при которых разница между суммой максимальных и минимальных будет минимальна

например для такой пары подойдут оба:

[
[1, 3, 0],
[2, 1, 4]
]

max(1 + 2, 3 + 1, 0 + 4)−min(1 + 2, 3 + 1, 0 + 4) = 1

если бы мы взяли только одну, то вышло max(1, 3, 0)−min(1, 3, 0) = 3, что не является минимальным, а значит не подходит

В данном примере

[
[0, 0, 5],
[0, 4, 0],
[0, 8, 0],
[2, 1, 0],
[3, 0, 0]
]

мы берем 1, 2, 4, 5 строки

max(0+0+2+3, 0+4+1+0, 5+0+0+0) − min(0+0+2+3, 0+4+1+0, 5+0+0+0) == 0 - является минимальным числом

в случае если есть несколько таких ситуаций, то нужно выбрать где сумма всех элементов будет больше

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

Answer 1

Теория

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

Заменим задачу на более простую: для данного набора списков требуется ответить есть ли комбинация с нулевой разницей или её нет. Ясно что если вы умеете решать общую задачу (про поиск минимальной разницы), то и эту решите без труда.

Рассмотрим списки из двух элементов. Например:

[0, 5]
[4, 0]
[8, 0]
[1, 0]

Заметим что если ко всем элементам конкретного списка прибавить одно и то же число, ответ останется прежним. Добавим к каждому списку такое число, чтобы первый элемент стал нулем:

[0,  5]
[0, -4]
[0, -8]
[0, -1]

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

5, -4, -8, -1

Это задача о сумме подмножеств:

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

Она NP-полная. То есть, она решается только полным перебором вариантов.

Раскручиваем цепочку назад. Если бы для исходной задачи существовало бы быстрое решение, то и задача проверки нулевой разницы для списков из двух элементов решалась бы быстро. Тогда и задача о сумме подмножеств решалась бы быстро. А это, скорее всего, невозможно - NP-полнота.

Ещё раз, коротко: задача может быть решена только полным перебором всех комбинаций.

Практика

Перебор написать не сложно:

def cost(s):
    return max(s) - min(s), -sum(s)


def search(a):
    m = len(a)
    n = len(a[0])
    s = [0] * n

    best_s = a[0]
    best_c = cost(a[0])
    
    def rec(i, empty):
        nonlocal best_s
        nonlocal best_c
        if i == m:
            if not empty:
                c = cost(s)
                if c < best_c:
                    best_s = s[:]
                    best_c = c
        else:
            rec(i + 1, empty)
            for j in range(n):
                s[j] += a[i][j]
            rec(i + 1, False)
            for j in range(n):
                s[j] -= a[i][j]

    rec(0, True)
    return best_s


def main():
    s = search([
        [1, 3, 0],
        [2, 1, 4]
    ])
    print(s, cost(s))

    s = search([
        [0, 0, 5],
        [0, 4, 0],
        [0, 8, 0],
        [2, 1, 0],
        [3, 0, 0]
    ])
    print(s, cost(s))


main()

$ python temp.py
[3, 4, 4] (1, -11)
[5, 5, 5] (0, -15)

БЛОГ НА HUSL

Определение максимальной суммы элементов при минимальной разнице сумм максимальных и минимальных подсписков

Ответы (1 шт):

Теория

Практика