Вариант на проблема с Knapsack: как да се реши проблемът за дял с подразделение Сума в Java

Актуализация: Прочетете за оптимизирането на сложността на пространството на решението за динамично програмиране в следващата ми статия тук.

Преди това писах за решаването на проблема с Knapsack (KP) с динамично програмиране. Можете да прочетете за това тук.

Днес искам да обсъдя вариант на KP: проблемът с подразделението с подмножество. За първи път видях този проблем в Leetcode - това ме подтикна да науча и да пиша за КП.

Това е изявлението на проблема (възпроизведено частично без примери):

Като се има предвид непразен масив, съдържащ само положителни числа, намерете дали масивът може да бъде разделен на две подмножества, така че сумата от елементите в двата подмножества да е равна.

За пълното изявление на проблема, с ограничения и примери, вижте проблема с Leetcode.

Динамично програмиране

Подобно на KP, ние ще решим това с помощта на динамично програмиране. Тъй като това е разновидност на КП, логиката и методологията до голяма степен са сходни.

Решение

Ние ще приютим нашето решение в метод, който връща булев - true, ако масивът може да бъде разделен на равни подмножества, а false в противен случай.

Стъпка 1: Пазене от нечетна сума от масив

Тривиално, ако всички числа в масива добавят нечетна сума, можем да върнем невярно. Продължаваме само ако масивът добави равномерна сума.

Стъпка 2: Създаване на таблицата

След това създаваме таблицата.

Редовете на таблицата представляват набора от елементи на масив, които трябва да бъдат разгледани, докато колоните на таблиците показват сумата, която искаме да достигнем. Стойностите на таблицата са просто булеви стойности, показващи дали може да се получи сума (колона) с набор от елементи на масив (ред).

По-конкретно, ред i представлява набор от масивни елементи от индекси 0 до (i-1). Причината за това компенсиране на 1 е, защото ред 0 представлява празен набор от елементи. Следователно ред 1 представлява първия елемент от масива (индекс 0), ред 2 представлява първите два елемента на масив (индекси 0-1) и т.н. Общо създаваме n + 1 реда, включително 0.

Искаме само да знаем дали можем да обобщим точно половината от общата сума на масива. Така че трябва само да създадем колони totalSum / 2 + 1, включително 0.

Стъпка 3: Предварително попълване на таблицата

Веднага можем да започнем да попълваме записите за основните случаи в нашата таблица - ред 0 и колона 0.

В първия ред всеки запис - с изключение на първия - трябва да е невярен. Спомнете си, че първият ред представлява празен набор. Естествено, ние не можем да достигнем нито една целева сума - номер на колоната - с изключение на 0.

В първата колона всеки запис трябва да е истина. Винаги можем, тривиално, да достигнем целева сума от 0, независимо от набора от елементи, с които трябва да работим.

Стъпка 4: Изграждане на таблицата (основен проблем)

Някои записи в таблицата в ред i и колона j са верни (постижими), ако е изпълнено едно от следните три условия:

  1. записът в ред i-1 и колона j е истина. Спомнете си какво представлява номерът на реда Следователно, ако успеем да постигнем определена сума с подмножество от елементи, които имаме в момента, можем да достигнем и тази сума с настоящия ни набор от елементи - просто да не използваме допълнителните елементи. Това е тривиално. Нека извикаме това prevRowIsTrue.
  2. Настоящият елемент е точно сумата, която искаме да постигнем. Това също е тривиално вярно. Нека се обадим това еExactMatch.
  3. Ако горните две условия не са изпълнени, имаме един останал начин да постигнем целевата си сума. Тук използваме текущия елемент - допълнителният елемент в набора от елементи в нашия текущ ред в сравнение с набора от елементи от предишния ред - и проверяваме дали сме в състояние да постигнем остатъка от целевата сума. Нека се обадим на този canArriveAtSum.

Нека разопаковаме условие 3. Можем да използваме текущия елемент само ако е по-малък от целевата ни сума. Ако те са равни, условие 2 ще бъде изпълнено. Ако е по-голям, не можем да го използваме Следователно, първата стъпка е да се гарантира, че текущият елемент <целева сума.

След като използваме настоящия ни елемент, ни остава остатъка от целевата ни сума. След това проверяваме дали това е постижимо, като проверяваме съответния запис в горния ред.

Както при обикновения КП, ние искаме постепенно да изградим нашата таблица отдолу нагоре. Започваме с основните случаи, докато стигнем до окончателното си решение.

Стъпка 5: Връщане на отговора

Ние просто връщаме връщане мат [nums.length] [totalSum / 2].

Работен код

Благодаря за четенето!