Варијација Кнапсацк проблема: како решити проблем партицијског једнаког подскупа на Јави

Раније сам писао о решавању проблема са напртњачом (КП) динамичким програмирањем. О томе можете прочитати овде.

Данас желим да разговарам о варијацији КП: проблем једнакости подскупа поделе. Први пут сам видео овај проблем на Леетцоде-у - то ме је подстакло да учим и пишем о КП-у.

Ово је изјава о проблему (репродукована делимично без примера):

С обзиром на непразан низ који садржи само позитивне читаве бројеве, пронађите да ли се низ може поделити на два подскупа тако да је збир елемената у оба подскупа једнак.

Потпуну изјаву о проблему, са ограничењима и примерима, погледајте у Леетцоде проблему.

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

Као и код КП, и ово ћемо решавати помоћу динамичког програмирања. Будући да је ово варијација КП-а, логика и методологија су углавном слични.

Решење

Наше решење ћемо сместити у методу која враћа логичку вредност - труе ако се низ може поделити на једнаке подскупове, а фалсе у супротном.

Корак 1: Заштита од непарне суме низа

Тривијално, ако се сви бројеви у низу зброје у непарне суме, можемо вратити фалсе. Настављамо само ако се низ збраја у паран збир.

Корак 2: Креирање табеле

Даље креирамо табелу.

Редови табеле представљају скуп елемената низа који треба узети у обзир, док ступци табеле означавају суму до које желимо доћи. Вредности табеле су једноставно логичке вредности, које указују на то да ли се може доћи до збира (колоне) са скупом елемената низа (ред).

Конкретно, ред и представља скуп елемената низа од индекса 0 до ( и -1). Разлог за ово померање 1 је зато што ред 0 представља празан скуп елемената. Према томе, ред 1 представља први елемент низа (индекс 0), ред 2 представља прва два елемента низа (индекси 0–1) итд. Укупно креирамо n + 1редове, укључујући 0.

Само желимо да знамо да ли можемо да саберемо тачно до половине укупног збира низа. Дакле, треба само да створимо totalSum / 2 + 1колоне, укључујући 0.

Корак 3: Претходно попуњавање табеле

Одмах можемо започети попуњавање уноса за основне случајеве у нашој табели - ред 0 и ступац 0.

У првом реду мора бити сваки унос - осим првог false. Подсетимо се да први ред представља празан скуп. Наравно, нисмо у могућности да дођемо ни до једне циљне суме - броја колоне - осим 0.

У првој колони сваки унос мора бити true. Увек можемо тривијално доћи до циљане суме од 0, без обзира на скуп елемената са којима морамо да радимо.

Корак 4: Израда табеле (суштина проблема)

Неки улазак у табели у реду сам , а колона Ј је true(остварива) ако је један од следећа три услова су задовољни:

  1. унос у реду и -1 и ступцу ј је true. Подсетите се шта представља редни број. Стога, ако смо у могућности да постигнемо одређену суму са подскупом елемената које тренутно имамо, ту суму можемо постићи и са нашим тренутним скупом елемената - једноставним коришћењем додатних елемената. Ово је тривијално. Назовимо ово prevRowIsTrue.
  2. Тренутни елемент је тачно збир који желимо да постигнемо. Ово је такође тривијално тачно. Назовимо ово isExactMatch.
  3. Ако горња два услова нису испуњена, преостаје нам још један начин да постигнемо циљну суму. Овде користимо тренутни елемент - додатни елемент у скупу елемената у нашем тренутном реду у поређењу са скупом елемената у претходном реду - и проверавамо да ли смо у стању да постигнемо остатак циљне суме. Назовимо ово canArriveAtSum.

Отпакујмо услов 3. Тренутни елемент можемо користити само ако је мањи од циљане суме. Ако су једнаки, услов 2 би био задовољен. Ако је већи, не можемо га користити. Према томе, први корак је осигурати да тренутни елемент <циљна сума.

Након употребе тренутног елемента, остаје нам остатак циљане суме. Затим проверавамо да ли је то могуће постићи провером одговарајућег уноса у горњем реду.

Као и код редовног КП-а, и ми желимо поступно да градимо своју табелу одоздо према горе. Почињемо са основним случајевима, док не дођемо до коначног решења.

Корак 5: Враћање одговора

Једноставно се враћамо return mat[nums.length][totalSum / 2].

Радни код

Хвала за читање!