Meet in the Middle

Sommige problemen hebben een N van ongeveer 40, waarbij alle 2^N deelverzamelingen proberen hopeloos is. De middenmethode biedt uitkomst voor zulke middelgrote gevallen. 🤝

Splits de invoer in twee helften. Los elke helft op met brute kracht en combineer daarna de twee gedeeltelijke resultaten op een slimme manier.

Twee helften van grootte N/2 kosten elk 2^(N/2) in plaats van in totaal 2^N. Die verkleining tot een vierkantswortel maakt van 2^40 een hanteerbare 2^20.

Vraag of een deelverzameling optelt tot een doelwaarde T. De som van een deelverzameling met N rond 40 is het schoolvoorbeeld van een probleem voor de middenmethode.

Noteer elke som van een deelverzameling uit de linkerhelft en sla ze op. Met N/2 elementen zijn dat slechts 2^(N/2) sommen.

Doe hetzelfde voor de rechterhelft en bouw de volledige lijst met sommen van deelverzamelingen op. Nu heb je twee hanteerbare lijsten.

Voor elke rechtersom r heb je een linkersom nodig die gelijk is aan T minus r. Met een verzameling of gesorteerde lijst kun je dat snel controleren.

Gebruik voor exacte doelen een hashverzameling. Sorteer voor aantallen of zo dicht mogelijke sommen één helft en zoek er binair in.

Het totale werk is ongeveer 2^(N/2) maal een logaritmische factor voor het zoeken of sorteren. Die complexiteit maakt een N rond 40 haalbaar.

Je slaat één volledige helft op, dus het geheugen groeit tot 2^(N/2). Bewaar alleen wat nodig is om binnen de limiet te blijven.

Gebruik het naast de som van een deelverzameling voor de maximale deelverzameling onder een bovengrens, het tellen van paren en problemen in de stijl van discrete logaritmen. Het werkt goed met een duidelijke splitsing.

Splits in twee helften, probeer elke helft met brute kracht en koppel daarna de linker- en rechtersom. Je ruilt een klein beetje geheugen in voor een enorme snelheidswinst. 🚀