Новый раздел по алгоритмам

Михаил Попов 09.12.2015 10:56 Python , Алгоритмы нет комментариев

Три рюкзака

Так вышло, что последние 2 месяца я прохожу курс по алгоритмам на stepic.org от CSC ну и благодаря курсу я узнал много нового и вспомнил много того, чего забыл. Пока память свежа, решил опубликовать решение одной из задач.

Условие задачи:

Разбить данные n натуральных чисел $%a_1,...,a_n$% на три части с равной суммой.

Например, множества, которые можно разбить на равные по сумме подмножества:

$%(1,1,1,2,2,2) o (1,2),(1,2),(1,2)$%
$%(1,2,3,4,5) o (1,4),(2,3),(5)$%
$%(1,2,3,4,4,5,8) o (1,8),(4,5),(2,3,4)$%

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

$%(1,1,1,2,2,3)$%

Также, если использовать жадный алгоритм и попытаться помещать числа, начиная с самых маленьких, то распределить множество $%(1,1,1,2,2,2)$% по 3-м корзинкам уже не удастся.

Вроде как простое условие задачи, но она под собой кроет, кажется фундаментальную проблему, по которой есть несколько статей и работ, к примеру такое описание этой задачи в Википедии.

Задача хорошо иллюстрирует пример динамического программирования.

На вход программе подается множество чисел через пробел. Если решение есть, программа выводит $%True$%. Если же решения нет, выводится $%False$%.

Чтобы определить, есть ли разбиение на 3 равные по сумме подпоследовательности, достаточно найти в заданной последовательности две не пересекающиеся подпоследовательности, такие что их суммы будут равны $%S/3$%. Тогда оставшиеся числа образуют подпоследовательность, сумма которой тоже равна $%S/3$%.

В качестве подзадачи возьмем следующую задачу: вычислить $%Part(i,s1,s2)$%, где значение функции $%Part$% будет равно $%True$% или $%False$%, $%i=0...n$%, $%s1$% и $%s2$% принимают значения $%0...S/3$%. Значение функции $%Part$% будет показывать, есть ли в последовательности чисел $%s_0, ...s_n$% подпоследовательности, суммы которых равны соответственно $%s1$% и $%s2$%. Построим рекуррентное соотношение для данной функции.

$%Part(i,s1,s2) = True$%, тогда и только тогда когда хотя бы одно из условий верно:

$%Part(i−1,s1,s2) = True$% - то есть если в последовательности чисел $%c_0,...,c_{i-1}$% существуют искомые подпоследовательности с суммами $%s1$% и $%s2$%, тогда при добавлении числа $%c_i$% эти подпоследовательности продолжат существовать;
$%Part(i−1,s1−c_i,s2) = True$% - то есть если в последовательности чисел $%c_0,...,c_{i-1}$% существуют искомые подпоследовательности с суммами $%s1−c_i$% и $%s2$%, тогда при добавлении числа $%c_i$% образуется подпоследовательность с суммой $%s1$%, а подпоследовательность с суммой $%s2$% продолжит существовать;
$%Part(i−1,s1,s2−c_i) = True$% - то есть если в последовательности чисел $%c_0,...,c_{i-1}$% существуют искомые подпоследовательности с суммами $%s1$% и $%s2−c_i$%, тогда при добавлении числа $%c_i$% подпоследовательность с суммой $%s1$% продолжит существовать, а подпоследовательность с суммой $%s2$% образуется за счет добавления числа $%c_i$%.

В итоге имеем рекуррентное соотношение:

$%Part(i,s1,s2) = Part(i−1,s1,s2) \lor P(i−1,s1−c_i,s2) \lor P(i−1,s1,s2−c_i)$%

По этому рекуррентному соотношению несложно написать рекурсивный алгоритм, но мы сразу напишем итеративный алгоритм, сохраняя последовательность вычисленных значений в 3-мерный список.

На Python решение задачи выглядит так:


def three_partition_bu(arr):
    n = len(arr)  # количество элементов множества
    s = sum(arr)  # сумма всех значений элементов множества

    # если сумма чисел множества не делится на 3 без остатка, то решения точно нет
    if s % 3 != 0:
        return False
    # сформируем пустой 3-мерный список
    D = [[[None for l in range(s + 1)] for j in range(s + 1)] for i in range(n + 1)]
    # Для подмножеств с суммой s1=s2=0 заполним решение значением True
    for i in range(n + 1):
        D[i][0][0] = True
    # Для множества с n=0 элементов заполним решение True, иначе False
    for s1 in range(s + 1):
        for s2 in range(s + 1):
            D[0][s1][s2] = (s1 == 0) and (s2 == 0)
    # Итеративно заполним все варианты решений для всех возможных составов подмножеств
    for i in range(1, n + 1):
        for s1 in range(0, s + 1):
            for s2 in range(0, s + 1):
                D[i][s1][s2] = D[i - 1][s1][s2] or D[i - 1][s1 - arr[i - 1]][s2] or D[i - 1][s1][s2 - arr[i - 1]]
    # Вернем значение в точке, где суммы подмножеств равны s//3
    return D[n][s//3][s//3]


def main():
    # Прочитаем значение с консоли
    arr = [int(i) for i in input().split(' ')]
    result = three_partition_bu(arr)
    print(result)

if __name__ == "__main__":
    main()

Данный алгоритм работает за время $%O(nS^2)$%, где $%S=\sum_{i=1}^{n}c_i$%. Это происходит потому, что мы проходим 3 вложенных цикла сначала по $%n$%, а потом два раза по $%S$%.

При этом это только решение, показывающее что числа в принципе можно разделить на 3 равные по сумме членов подмножества, теперь нужно эти подмножества восстановить.

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

Еще немного ссылок на работы по этой теме:

Наибольшая невозрастающая подпоследовательность

Как заработать в интернете

0 0