Una variació del problema de la motxilla: Com solucionar el problema "Partició igual subconjunt" a Java

Actualització: podeu trobar informació sobre l’optimització de la complexitat espacial de la solució de programació dinàmica al meu article següent aquí.

Abans d’això, vaig escriure sobre la resolució del problema Knapsack (KP) amb programació dinàmica. Podeu llegir-ho aquí.

Avui vull parlar d’una variació de KP: el problema de la partició és igual a la suma del subconjunt. Vaig veure aquest problema per primera vegada a Leetcode: aquesta era la raó per conèixer KP i escriure sobre això.

Aquest és el problema (parcialment reproduït sense exemples):

Per a una matriu no buida que conté només nombres enters positius, heu de determinar si la matriu es pot dividir en dos subconjunts de manera que la suma dels elements sigui la mateixa als dos subconjunts.

Podeu trobar la descripció completa del problema amb restriccions i exemples al problema Leetcode.

Programació dinàmica

Igual que amb KP, solucionem això amb programació dinàmica. Com que és una variació de KP, la lògica i la metodologia són en gran mesura similars.

Solució

Situarem la nostra solució en un mètode que retorni un valor booleà - cert si la matriu es pot dividir en subconjunts iguals, fals en cas contrari.

Pas 1: protecció contra el total d’arranjament estrany

Trivialment, podem tornar falsos si tots els nombres de la matriu se sumen a una suma estranya. Només procedim si la matriu és una suma uniforme.

Pas 2: creació de la taula

A continuació, creem la taula.

Les files de la taula representen la quantitat d'elements de matriu a considerar, mentre que les columnes de la taula indiquen la suma a què volem arribar. Els valors de la taula són simplement valors booleans que indiquen si una suma (columna) es pot determinar mitjançant una sèrie d’elements de matriu (fila).

Concretament, la fila i representa un conjunt d’elements de matriu des dels índexs 0 a (i-1). El motiu d'aquesta compensació de 1 és que la fila 0 representa un conjunt buit d'elements. Per tant, la fila 1 significa el primer element de matriu (índex 0), la fila 2 per als dos primers elements de matriu (índexs 0-1), etc. En total, creem n + 1 files, inclosa 0.

Només volem saber si podem resumir exactament la meitat del total de la matriu. Així que només necessitem crear columnes totalSum / 2 + 1 incloent-hi 0.

Pas 3: ompliu prèviament la taula

Podem començar immediatament emplenant les entrades dels casos base de la nostra taula: fila 0 i columna 0.

En la primera línia, totes les entrades (a excepció de la primera) han de ser incorrectes. Recordeu que la primera línia representa un conjunt buit. Per descomptat, no podem determinar una suma objectiu (número de columna) diferent de 0.

A la primera columna, totes les entrades han de ser certes. Podem assolir trivialment un total de 0 objectius independentment de la quantitat d’elements amb què necessitem treballar.

Pas 4: creació de la taula (el nucli del problema)

Una entrada de la taula de la fila i de la columna j és veritable (accessible) si es compleix una de les tres condicions següents:

  1. L’entrada a la fila i-1 i a la columna j és certa. Recordeu què representa el número de línia. De manera que si podem obtenir una certa suma amb un subconjunt dels elements que tenim actualment, també podem obtenir aquesta suma amb el nostre conjunt d’elements actuals, simplement no utilitzant els elements addicionals. És trivial. Anomenem això prevRowIsTrue.
  2. L’element actual és exactament la suma que volem aconseguir. Això també és trivialment cert. Anomenem això "isExactMatch".
  3. Si no es compleixen les dues condicions anteriors, encara tenim la manera d’arribar a la suma objectiu. Aquí utilitzem l’element actual (l’element addicional del conjunt d’elements de la nostra fila actual en comparació amb el conjunt d’elements de la fila anterior) i comprovem si podem arribar a la resta de la suma objectiu. Anomenem-ho a canArriveAtSum.

Desempaquetem la condició 3. Només podem fer servir l’actualitat si està per sota del nostre objectiu. Si fossin iguals, es compliria la condició 2. Si és més gran, no la podem fer servir. El primer pas és, doncs, assegurar-se que l’element actual

Després d'utilitzar el nostre producte actual, resta la resta de la quantitat objectiu. A continuació, comprovem si es pot aconseguir comprovant l’entrada corresponent a la línia anterior.

Com en el KP normal, volem construir la nostra taula pas a pas de baix a dalt. Comencem pels casos bàsics fins arribar a la nostra solució final.

Pas 5: retorna la resposta

Acabem de retornar la estora de retorn [longituds.noms] [totalSum / 2].

Codi de treball

Gràcies per llegir!