Вариация на проблема с Knapsack: как да решим проблема с дяла на равното подмножество в Java

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

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

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

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

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

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

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

Решение

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

Стъпка 1: Защита срещу нечетна сума от масив

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Просто се връщаме return mat[nums.length][totalSum / 2].

Работен код

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