Сбалансированный раздел жадный подход

Question

Я смотрел на проблему сбалансированного разбиения здесь и здесь (проблема 7).

В основном проблема состоит в том, чтобы разбить данный массив чисел на 2 подмножества (S1 и S2), так чтобы абсолютная разница между суммами чисел составляла S1 и S2. |sum(S1) - sum(S2)| должен быть минимальным. Одна вещь, которую я не понял, почему никто не предлагает жадный подход:

def balanced_partition(lst):
    idx = 0
    S1 = 0
    S2 = 0
    result_partition=[None]*len(lst)
    while idx < len(lst):
        new_S1 = S1 + lst[idx]
        new_S2 = S2 + lst[idx]
        if abs(new_S1 - S2) < abs(new_S2 - S1):
            result_partition[idx] = 1
            S1 = new_S1
        else:
            result_partition[idx] = 2
            S2 = new_S2
        idx += 1
    print("final sums s1 = {S1} and s2 = {S2} ".format(S1=S1, S2=S2))
    return result_partition

Что не так с моим подходом? Кажется, он прошел все тесты, которые я могу придумать.

Answer 1

Простой контрпример [1,1,1,1,1,1,6], Жадный подход распределит те между двумя наборами, в то время как оптимальное решение [1,1,1,1,1,1],[6],

Answer 2

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

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

Вопрос в том, когда использовать жадный или динамический подход к программированию. Я выполнил некоторое конкурентное программирование, и когда я вижу проблему DP (проблемы, такие как разбиение, подмножество сумм, рюкзак и т. Д.), Я иногда сразу придумываю жадное решение, потому что в большинстве случаев они более очевидны. Люди используют жадный подход все время в повседневной жизни. Перед реализацией я проверяю свой алгоритм на примерах, и, если я убедлю себя, что это правильный подход, я его реализую. Это в некотором роде интуитивно понятно.

Если вы найдете тестовый пример, который должен иметь лучший ответ, скорее всего, это означает, что вам нужно найти решение DP. Если вы получили WA от системы судьи, это означает, что вы не нашли хороших тестовых случаев, но ничего страшного, вам не нужно находить этот точный тестовый случай, потому что он не поможет вам найти лучшее решение.