Разнавіднасць праблемы Knapsack: Як вырашыць праблему "Partition Equal Subset Sum" у Java

Абнаўленне: інфармацыю пра аптымізацыю прасторавай складанасці рашэння дынамічнага праграмавання можна знайсці ў наступным артыкуле.

Да гэтага я пісаў пра вырашэнне праблемы Knapsack (KP) з дынамічным праграмаваннем. Пра гэта можна прачытаць тут.

Сёння я хацеў бы абмеркаваць варыянт КП: праблема падзелаў роўная падмнозе. Я ўпершыню ўбачыў гэтую праблему ў Leetcode - гэта стала прычынай пазнаёміцца ​​з КП і напісаць пра яе.

Гэта праблема (часткова прайграная без прыкладаў):

Для непустога масіва, які змяшчае толькі станоўчыя цэлыя лікі, вам трэба вызначыць, ці можна масіў падзяліць на два падмножыны, каб сума элементаў была аднолькавай у абедзвюх падмноствах.

Поўнае апісанне праблемы з абмежаваннямі і прыкладамі можна знайсці ў праблеме Leetcode.

Дынамічнае праграмаванне

Як і ў KP, мы вырашаем гэта з дапамогай дынамічнага праграмавання. Паколькі гэта варыянт КП, логіка і метадалогія шмат у чым падобныя.

Рашэнне

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

Крок 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. Бягучы элемент - гэта менавіта тая сума, якую мы хочам дасягнуць. Гэта таксама банальна дакладна. Давайце назавем гэта "isExactMatch".
  3. Калі вышэйзгаданыя дзве ўмовы не выкананы, у нас усё яшчэ ёсць спосаб дасягнуць нашай мэтавай сумы. Тут мы выкарыстоўваем бягучы элемент - дадатковы элемент у наборы элементаў у нашым бягучым радку ў параўнанні з наборам элементаў у папярэднім радку - і правяраем, ці зможам мы дасягнуць астатняй мэты. Давайце назавем гэта canArriveAtSum.

Давайце распакуем умову 3. Мы можам выкарыстоўваць бягучы элемент толькі ў тым выпадку, калі ён ніжэйшы за агульную мэты. Калі яны супадаюць, умова 2 будзе выканана. Калі яна большая, мы не можам гэтым скарыстацца. Такім чынам, першы крок - пераканацца ў наяўнасці бягучага пункта

Пасля таго як мы выкарыстоўваем наш бягучы тавар, астатняя частка нашай мэтавай сумы застаецца. Затым мы правяраем, ці можна гэтага дасягнуць, праверыўшы адпаведны запіс у радку вышэй.

Як і ў звычайным КП, мы хочам стварыць нашу табліцу крок за крокам знізу ўверх. Мы пачынаем з асноўных выпадкаў, пакуль не прыйдзем да нашага канчатковага рашэння.

Крок 5. Вярніце адказ

Мы проста вяртаем дыванок вяртання [nums.length] [totalSum / 2].

Працоўны код

Дзякуй за чытанне!