Subset sum en partition

Gegeven getallen en een doel: kan een deelverzameling precies dat doel vormen? Dit is een knapzakprobleem waarbij waarde gelijk is aan gewicht.

Hier houd je bereikbaarheid bij, geen maximum. Laat dp[s] True zijn wanneer een deelverzameling precies s als som heeft.

De lege deelverzameling heeft nul als som, dus dp[0] begint als True. Elke andere som begint als False totdat een getal bewijst dat die bereikbaar is.

Markeer voor elk getal s als bereikbaar als s - num dat al was. Eén getal kan veel sommen naar True veranderen.

Elk getal mag hoogstens één keer worden gebruikt, dus de binnenste lus loopt achteruit, net als bij het 0/1-knapzakprobleem. Vooruitgaan zou een getal hergebruiken.

Na het verwerken van alle getallen geeft dp[target] antwoord op de vraag. True betekent dat er een geldige deelverzameling bestaat; False betekent dat dit onmogelijk is.

Het partitieprobleem vraagt: kun je de array opsplitsen in twee delen met dezelfde som? Het is rechtstreeks terug te brengen tot deelverzamelingssom.

Als de totale som oneven is, zijn gelijke helften onmogelijk en antwoord je meteen nee. Anders is het doel eenvoudigweg total // 2.

Vraag nu alleen of een deelverzameling total // 2 bereikt. Als één helft het doel bereikt, vormt de rest automatisch de bijbehorende tweede helft.

De kosten zijn van orde n maal het doel, een pseudopolynomiale bovengrens. Het is snel als het doel klein is en traag als de sommen enorm zijn.

Som van deelverzamelingen, partitie en het 0/1-rugzakprobleem delen één motor. Herken het patroon van nemen of overslaan en gebruik dezelfde lus opnieuw.

Je hebt de som van een deelverzameling opgelost met booleaanse DP en een lus achteruit, en het partitieprobleem teruggebracht tot het bereiken van total // 2. Dezelfde motor, nieuwe winst. ✅