Сумма подмножества и разбиение

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

Здесь нужно отслеживать достижимость, а не максимум. Пусть dp[s] равно True, если существует подмножество с суммой ровно s.

Пустое подмножество имеет сумму ноль, поэтому dp[0] изначально равно True. Все остальные суммы начинаются со значения False, пока какое-либо число не сделает их достижимыми.

Для каждого числа отметьте s как достижимую сумму, если s - num уже была достижима. Одно число может сделать истинными сразу несколько сумм.

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

После обработки всех чисел dp[target] отвечает на вопрос. True означает, что подходящее подмножество существует, а False — что это невозможно.

Задача о разбиении спрашивает: можно ли разделить массив на две части с одинаковой суммой? Она напрямую сводится к задаче о сумме подмножества.

Если общая сумма нечётная, равные части невозможны, поэтому сразу ответьте «нет». Иначе целевая сумма — это просто total // 2.

Теперь просто проверьте, может ли подмножество дать total // 2. Если одна часть достигает цели, оставшиеся элементы автоматически образуют соответствующую вторую часть.

Стоимость составляет порядка n, умноженного на target, — это псевдополиномиальная оценка. Алгоритм работает быстро при небольшой цели и медленно при огромных суммах.

Задачи о сумме подмножеств, разбиении и рюкзаке 0/1 используют один механизм. Распознайте схему «взять или пропустить» — и сможете повторно использовать тот же цикл.

Проверьте сведение задачи о разбиении.

Вы решили задачу о сумме подмножеств с помощью логического DP и обратного цикла, а затем свели задачу о разбиении к достижению значения total // 2. Тот же механизм — новые победы. ✅