/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
Matematisk problem
Fra : Hansen


Dato : 26-09-06 12:25

Hejsa!

Jeg ledte efter en matematik gruppe uden held, så gætter på at denne gruppe
er det bedste bud.

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.

Giver det mening eller er det sort snak? Håber der er nogen der kan lede mig
på rette spor. Det skal siges at tabellen er sorteret således at det største
tal kommer forrest.

/Hansen



 
 
Martin R. Ehmsen (26-09-2006)
Kommentar
Fra : Martin R. Ehmsen


Dato : 26-09-06 13:11

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hansen wrote:
> 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.

Du kan kigge her:
http://en.wikipedia.org/wiki/Subset_sum

Martin R. Ehmsen
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFFGRjhoCiIG96jYfYRArK6AJ96shsYBEMYi/jBbcLVYjLhpbAGFQCfTRaH
0A8jwOKwGwo12d9bH2tSaIo=
=+50K
-----END PGP SIGNATURE-----

Thorbjørn Ravn Ander~ (26-09-2006)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 26-09-06 14:34

"Hansen" <bluesboys@-remove-this-hotmail.com> writes:

> 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.

Kan du ikke lige se om dit problem svarer til "Knapsack"-problemet
(fyldning af rygsæk).

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

Bedste resultat kræver afprøvning af alle kombinationer (NP-komplet),
men den grådige algoritme på siden er hurtig og nem og giver gode
resultater i de fleste tilfælde.

Sorter i faldende orden (eller tag din liste bagfra).

Hvis største element kan være i rygsækken, så brug det, ellers forkast
det.

Gentag med næststørste indtil du har været alle igennem.
--
Thorbjørn Ravn Andersen

Torben Ægidius Mogen~ (26-09-2006)
Kommentar
Fra : Torben Ægidius Mogen~


Dato : 26-09-06 14:42

"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


Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408847
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste