[algoritme] benadering getal met reeks

[Shadowfox]

Heeft er iemand een idee of er een algoritme bestaat om een getal te vormen door optelling van getallen uit een gegeven reeks, dat het dichtst ligt bij een opgegeven getal. Het getal dat uit de bus komt moet zo dicht mogelijk tegen het doelgetal liggen, indien het mogelijk is zelfs erop.

Het dient om een studietraject van een hogeschoolstudent te bepalen. Elk vak heeft een bepaald aantal studiepunten en het stukje code zou een suggestie moeten doen voor een traject. Elk traject is goed, zolang het maar zo dicht tegen de grens ligt.

VB reeks: 5-4-8-4-6-6-2-3

te benaderen getal: 14

mogelijke oplossingen zijn bvb(allen even goed):

8+6;

8+2+4;

5+2+3+4

[Phys]

En bij de reeks 5,5,5,5,5,5,5,5 met doelgetal 1? Is 5 dan de beste oplossing?

[Cycloon]

Sorteer de getallen van klein naar groot en zoek dan alle oplossingen door middel van backtracking. Vanaf je aan een som komt die te groot wordt keer je terug naar de vorige stap en ga je verder met een ander getal.

http://en.wikipedia.org/wiki/Backtracking