Ik heb problemen met het maken van een formule in excel. Is er een formule die uit een reeks getallen, die getallen haalt die een vooropgestelde som vormen?

Antwoord

Bij mijn weten kan je dit niet in een Excel formule gieten, en moet je hiervoor aan het werk in een programmeertaal - als het absoluut in Excel moet kan het waarschijnlijk wel in VBA.

Voordat u begint met programmeren moet ik het volgende zeggen: dit probleem is equivalent aan het "subset sum probleem". Het is een speciaal geval van wat in de theoretische informatica bekend als het "knapsack problem" (knapzakprobleem), en is wat men in vakjargon noemt "NP-compleet". In de praktijk betekent dit dat het wel mogelijk is om een oplossing te programmeren, maar dat die oplossing in de regel heel slecht schaalbaar is. Met andere woorden: het kan zijn dat je dit kan oplossen in 1 seconde voor 20 getallen, terwijl je met 30 getallen een jaar aan het rekenen bent.

Een oplossing kan wel geprogrammeerd worden, deze is eenvoudig: probeer alle mogelijke combinaties van getallen uit (= brute-forcing). Eens je een oplossing gevonden hebt, is die ook heel eenvoudig te controleren: het is correct of het is niet correct, gewoon de som maken is voldoende. Maar als je een grote hoeveelheid getallen hebt, kan het je jaren duren om alle combinaties te overlopen en uit te rekenen. Dit is een typische eigenschap van de zogenaamde NP-complete problemen: de oplossing is moeilijk te vinden, maar gemakkelijk te verifieren.

Dat het niet efficient is om op die manier een oplossing te zoeken is wel duidelijk, maar het is vooralsnog de enige bekende manier om een exacte oplossing te krijgen. Dit is een probleem dat in de geschiedenis erg gedetailleerd bestudeerd is. Een van de grote onopgeloste vraagstukken in de informatica is of er wel een snelle en schaalbare methode bestaat voor dit soort, op het eerste zicht erg eenvoudige, problemen.

Er bestaan verschillende benaderende oplossingen die wel goed presteren, maar vaak alleen in speciale gevallen (met behulp van Dynamic Programming algoritmes bvb). Als je erg vertrouwd bent met VBA voor Excel en niet bang bent van een paar honderd lijnen code, kan je die uitdaging wel aangaan. Er is oude C-code te vinden op de website die ik als link bij dit antwoord heb bijgevoegd, je bent waarschijnlijk het best met de "decomp" routine op die website, maar je kan ook kijken naar de code voor 0-1 knapsack problems.

Maar persoonlijk ben ik geneigd om te zeggen: hou het eenvoudig en brute-force het met VBA, maar bouw zeker beveiligingen in zodat je programma niet eindeloos doorrekent als je het per ongeluk een te grote reeks getallen geeft. Het aantal getallen dat je kan meegeven als je het berekenbaar wil houden, zal vermoedelijk sowieso heel erg laag zijn. Als je op grote getallenreeksen moet werken, ben ik zelf geneigd om te zeggen: laat de automatisatie voor wat het is en doe een beredeneerde gok met het blote oog. Mensen zijn immers uitzonderlijk goed in staat om zonder computer vrij goede benaderende oplossingen te vinden voor dit soort problemen.