"Hansen" <bluesboys@-remove-this-hotmail.com> writes:
> Det jeg leder efter er en algoritme til at give mig den sum (ud fra en
> tabel) der kommer tættest på et givet tal (kun under, ikke over).
>
> Altså hvis nu det givne tal er 21 og jeg har en tabel med tallene
> {13,12,12,10,10}, så leder jeg efter en metode til at finde frem til at det
> er 10 og 10. Metoden skal kunne bruges når der er mellem 1 og 12 tal (inkl)
> i tabellen.
>
> Problemet er at det ikke er nok for mig at finde den sum der kommer tættest
> på, men også at identificere hvilke(t) tal der udgør summen.
Nå så du vil spille Blackjack?
Som Martin sagde, så er problemet beslægtet med subset sum problemet,
som er NP-komplet, dvs. at det tager meget lang tid at beregne, hvis
der er mange tal i tabellen. Hvis køretiden ikke betyder så meget,
kan du bruge følgende metode:
1. Generer alle delmængder i en eller anden rækkefølge.
2. Beregn summen for hver af disse.
3. Sorter mængderne efter faldende sum.
4. Vælg den første, der ikke overskrider dit måltal.
Denne metode kræver, at du har alle delmængderne lagret, og det kan
fylde en del. Så det er måske bedre at smide dem væk efterhånden, som
de bliver genereret. Det betyder så, at man ikke kan sortere dem, så
i stedet kan du starte med at lede efter delmængder, der har sum lig
med dit måltal, og hvis det ikke lykkes så tal en under dit måltal
osv. Hvis dit måltal er lille, så skulle det ikke tage voldsomt meget
længere tid. Hermed har du reduceret dit problem til subset sum. Et
(ikke-effektivt) program til dette er herunder:
subsetsum sum set = sss sum set []
sss 0 set subset = [subset]
sss sum [] subset = []
sss sum (x:xs) subset
= if x>sum then sss sum xs subset
else sss (sum-x) xs (x:subset) ++ sss sum xs subset
Dette program (skrevet i Haskel) giver dig alle delmængder, der har
den givne sum. For at søge efter det største tal, der ikke
overskrider dit mål (og den tilhørende mængde), kan du definere
funktionen
largest 0 set = (0,[])
largest t set
= case (subsetsum t set) of
[] -> largest (t-1) set
(subset:_) -> (t,subset)
Så får du f.eks. at largest 21 [13,12,12,10,10] giver dig (20,[10,10]).
Torben