Почему жадный алгоритм оптимален?

Codility, урок 14, задание TieRopes (https://codility.com/demo/take-sample-test/tie_ropes). Короче говоря, задача состоит в том, чтобы разбить список A положительных целых чисел на максимальное количество (непрерывных) подсписков, сумма которых не меньше K.

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

int solution(int K, vector<int> &A) {
    int sum = 0, count = 0;
    for (int a : A)
    {
        sum += a;
        if (sum >= K)
        {
            ++count;
            sum = 0;
        }
    }
    return count;
}

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


algorithm greedy proof
person NPS    schedule 08.10.2014    source источник
comment
Обычный шаблон для доказательства оптимальности жадного алгоритма состоит в том, чтобы (1) постулировать случай, когда жадный алгоритм не дает оптимального результата; (2) посмотрите на первое место, где его решение и оптимальное решение расходятся; и (3) доказать, что это место не может существовать. Доказательство от противного.   -  person Sneftel    schedule 08.10.2014
comment
Мне кажется, что требование concontinuity уже устраняет всю значимую гибкость решения этой проблемы. т.е. решение очевидно и просто: просто накапливайте раздел с самого начала, пока не получите K, а затем запустите новый раздел. Единственная гибкость, которую он допускает, — это продолжать расширять текущий раздел, когда его сумма уже равна K, но сразу видно, что это только снизит качество решения.   -  person AnT    schedule 08.10.2014
comment
@AndreyT Это твоя интуиция, и ты, вероятно, прав, но я не думаю, что этого достаточно для доказательства.   -  person NPS    schedule 08.10.2014
comment
@NPS: Да, здесь я могу ошибаться. Я предположил, что нам не разрешено пропускать элементы между разделами. Но, видимо, мы. Тогда есть еще одна гибкость. Мы можем пожертвовать (пропустить) несколько начальных элементов и начать накапливать первый раздел из какого-то более позднего элемента. То же самое можно сделать между разделами. Есть ли у него шанс найти лучшее решение?   -  person AnT    schedule 08.10.2014

Ответы (2)


arrow_upward
4
arrow_downward

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

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

Теперь давайте подумаем о разделе, который будет создавать жадный алгоритм, скажем, P2. Есть две вещи, которые могут произойти для первого подсписка в P2:

  1. Это может быть то же самое, что и первый подсписок в P1.
  2. Он может быть короче первого подсписка в P1.

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

В 2. вы бы тоже повторили рассуждения, но теперь у вас есть хотя бы один «лишний» предмет. Итак, опять же, следующий подсписок может:

2.1. Дойти до следующего подсписка в P1.
2.2. Конец перед следующим подсписком в P1.

И повторить. Таким образом, в любом случае у вас будет минимум столько же подсписков, сколько P1. Это означает, что P2 как минимум так же хорош, как и любой возможный раздел списка, и, в частности, любой оптимальный раздел.

Это не очень формальная демонстрация, но я думаю, что она действительна. Пожалуйста, укажите все, что, по вашему мнению, может быть неправильным.

person jdehesa    schedule 08.10.2014
comment
Я тоже так думаю об этой проблеме. По сути, вы можете показать, что для любого оптимального решения, имеющего k подсписков, жадное решение также имеет по крайней мере k подсписков, каждая из первых позиций которых равна ‹= соответствующим первым позициям в оптимальном решении. (Одна опечатка: должно быть. Он может быть короче первого подсписка в P1, а не... в P2.) - person j_random_hacker; 08.10.2014

arrow_upward
1
arrow_downward

Вот идеи, которые приводят к формальному доказательству.

  1. Если A является суффиксом B, то максимальный размер раздела для A меньше или равен максимальному размеру раздела для B, потому что мы можем расширить первый подсписок раздела A, чтобы включить новые элементы без уменьшения его суммы.

  2. Сумма каждого правильного префикса каждого подсписка в жадном решении меньше K.

  3. Нет смысла делать пробелы, потому что мы можем добавить недостающие элементы в соседний список (я думал, что моя формулировка вопроса исключает такую ​​возможность по определению, но все же скажу).

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

Базис i = 0 тривиален, так как подойдет произвольное оптимальное решение. Индуктивный шаг состоит в поиске оптимального решения, согласующегося с жадным подсписком, в первых i подсписках, а затем уменьшении i+1го подсписка, чтобы он соответствовал жадному решению (согласно наблюдению 2, мы действительно сокращаем этот подсписок, поскольку он начинается в той же позиции, что и жадный подсписок). ; по наблюдению 1 мы можем соответственно расширить i+2th подсписок оптимального решения).

person David Eisenstat    schedule 08.10.2014
comment
Боюсь, я не понимаю вашего пункта № 2 - ни почему это должно быть правдой, ни почему это полезно! Остальное имеет смысл, но я думаю, что также нужно явно сказать, что первый подсписок в любом оптимальном решении не может быть короче, чем первый подсписок в жадном решении, чтобы объяснить, почему единственный случай, с которым мы имеем дело на шаге индукции состоит в том, чтобы уменьшить (i+1)-й подсписок оптимального решения (то есть, почему нам никогда не нужно их увеличивать). - person j_random_hacker; 08.10.2014
comment
@j_random_hacker Я имел в виду именно это, и я согласен, что предыдущая формулировка была плохой. - person David Eisenstat; 08.10.2014
comment
Теперь мне стало понятнее, спасибо. FWIW Я не думаю, что пункт № 3 нужен; раздел в вопросе ОП говорит мне, что ни одно решение не может содержать пробел, и пробелы не появляются во время жадной конструкции. (Меня также озадачивает упоминание об этом dasblinkenlights.) Пока я придираюсь: запись только в единственном решении, которое согласуется с жадным, является жадным, похоже, намекает на то, что жадное решение может быть уникальным, но это не так (и не нужно быть); AFAICT, все, что нужно, это найти соответствующее оптимальное решение, когда i = opt_number_of_sublists. - person j_random_hacker; 08.10.2014