En variation på Knapsack-problemet: hvordan man løser problemet Partition Equal Subset Sum i Java

Tidligere skrev jeg om at løse Knapsack Problem (KP) med dynamisk programmering. Du kan læse om det her.

I dag vil jeg diskutere en variation af KP: partitionens lige delmængde sumproblem. Jeg så først dette problem på Leetcode - det var det, der fik mig til at lære om og skrive om KP.

Dette er problemstillingen (gengivet delvist uden eksempler):

Givet et ikke-tomt array, der kun indeholder positive heltal, skal du finde ud af, om arrayet kan opdeles i to delmængder, således at summen af ​​elementer i begge delmængder er ens.

For den fulde problemangivelse med begrænsninger og eksempler, se Leetcode-problemet.

Dynamisk programmering

Ligesom med KP løser vi dette ved hjælp af dynamisk programmering. Da dette er en variation af KP, er logikken og metoden stort set ens.

Opløsning

Vi vil huse vores løsning i en metode, der returnerer en boolsk - sandt, hvis arrayet kan opdeles i lige store delmængder og ellers falsk.

Trin 1: Beskyttelse mod ulige array-sum

I det væsentlige, hvis alle numrene i arrayet udgør en ulige sum, kan vi returnere false. Vi fortsætter kun, hvis arrayet tilføjer en jævn sum.

Trin 2: Oprettelse af bordet

Dernæst opretter vi tabellen.

Tabelrækker repræsenterer det sæt matrixelementer, der skal overvejes, mens tabelkolonner angiver det beløb, vi vil nå frem til. Tabelværdier er simpelthen boolske værdier, der angiver, om en sum (kolonne) kan nås med et sæt matrixelementer (række).

Konkret repræsenterer række i et sæt matrixelementer fra indeks 0 til ( i -1). Årsagen til denne forskydning på 1 er, at række 0 repræsenterer et tomt sæt af elementer. Derfor repræsenterer række 1 det første matrixelement (indeks 0), række 2 repræsenterer de to første matrixelementer (indeks 0–1) osv. I alt opretter vi n + 1rækker inklusive 0.

Vi vil kun vide, om vi kan opsummere nøjagtigt til halvdelen af ​​den samlede sum af arrayet. Så vi behøver kun at oprette totalSum / 2 + 1kolonner inklusive 0.

Trin 3: Forudfyldning af tabellen

Vi kan straks begynde at udfylde posterne til basissagerne i vores tabel - række 0 og kolonne 0.

I første række skal hver post - undtagen den første - være false. Husk at den første række repræsenterer et tomt sæt. Vi er naturligvis ikke i stand til at nå frem til noget målsum - kolonnenummer - undtagen 0.

I den første kolonne skal hver post være true. Vi kan altid, trivielt, nå frem til en målsum på 0, uanset sæt af elementer, vi skal arbejde med.

Trin 4: Opbygning af bordet (kernen i problemet)

Nogle indtastninger i tabellen i række i og kolonne j er true(opnås), hvis en af ​​de følgende tre betingelser er opfyldt:

  1. posten i række i -1 og kolonne j er true. Husk hvad række nummer repræsenterer. Derfor, hvis vi er i stand til at opnå en bestemt sum med en delmængde af de elementer, som vi har i øjeblikket, kan vi også opnå denne sum med vores nuværende sæt af elementer - ved simpelthen ikke at bruge de ekstra elementer. Dette er trivielt. Lad os kalde det prevRowIsTrue.
  2. Det aktuelle element er nøjagtigt den sum, vi ønsker at opnå. Dette er også trivielt sandt. Lad os kalde det isExactMatch.
  3. Hvis ovenstående to betingelser ikke er opfyldt, har vi en tilbageværende måde at nå vores målsum på. Her bruger vi det aktuelle element - det ekstra element i sættet af elementer i vores aktuelle række sammenlignet med sættet af elementer i den foregående række - og kontrollerer, at vi er i stand til at nå den resterende del af målsummen. Lad os kalde det canArriveAtSum.

Lad os pakke betingelse 3. Vi kan kun bruge det aktuelle element, hvis det er mindre end vores målsum. Hvis de er lige, ville betingelse 2 være opfyldt. Hvis det er større, kan vi ikke bruge det. Derfor er det første trin at sikre, at det aktuelle element <målsum.

Efter at have brugt vores nuværende element, står vi tilbage med resten af ​​vores målsum. Vi kontrollerer derefter, om det er muligt, ved at kontrollere den tilsvarende post i rækken ovenfor.

Som med almindelig KP ønsker vi gradvist at opbygge vores bord nedenfra og op. Vi starter med basissagerne, indtil vi når frem til vores endelige løsning.

Trin 5: Returner svaret

Vi vender simpelthen tilbage return mat[nums.length][totalSum / 2].

Arbejdskode

Tak for læsningen!