Hoi UB'ers,
Ik heb een reeks mappen waarvan ik de grootte per map heb, gesorteerd (aflopend of oplopend) in een CSV.
Nu zou ik graag een mogelijkheid vinden om een som te maken van alle mappen zodat het geheel het dichts bij een bepaalde capaciteit (bvb USB stick) komt.
Gesorteerd van kleinste naar grootste en optellen tot je tegen limiet aan zit gebruik ik nu. Maar het is bvb perfect mogelijk dat ipv het laatste getal op te tellen het volgende getal kan nemen.
Bvb stel dat de maximale capaciteit 11 is
1 + 2 + 3 + 4 = 10
maar 1 + 2 + 3 + 5 = 11
2de som ligt dus dichter bij maximale capaciteit
Soit, het lijkt me dus een wiskundig probleem.
Idealitair zouden dus van de gegeven cijfers alle mogelijke som combinaties moeten gemaakt worden en dat daarvan degene overblijft die het dichtst bij de maximale capaciteit zit.
Iemand idee hoe je zoiets aanpakt? Mag in Excel, Powershell script, Bash script,...
Alvast bedankt!
Wiskundig probleempje
-
cloink
- Elite Poster
- Berichten: 3515
- Lid geworden op: 29 okt 2007, 10:29
- Twitter: cloink
- Uitgedeelde bedankjes: 93 keer
- Bedankt: 137 keer
- Contacteer:
Yep, bovenstaande manier (groot -> klein) zou prima moeten werken!
Let wel: zo zou het natuurlijk kunnen dat je bepaalde sticks hebt met een klein aantal grote files en dan enkele sticks met een belachelijke hoeveelheid aan kleine files, m.a.w. dat algoritme gaat niet echt netjes balanceren. Als je dat wil, zou je eerst onderverdelingen moeten maken (alle files tussen x en y, daarnaast alle files tussen y en z, enz. en dan bv. slechts max. X files uit de grootste nemen o.i.d.).
Let wel: zo zou het natuurlijk kunnen dat je bepaalde sticks hebt met een klein aantal grote files en dan enkele sticks met een belachelijke hoeveelheid aan kleine files, m.a.w. dat algoritme gaat niet echt netjes balanceren. Als je dat wil, zou je eerst onderverdelingen moeten maken (alle files tussen x en y, daarnaast alle files tussen y en z, enz. en dan bv. slechts max. X files uit de grootste nemen o.i.d.).
ooh. shiny.
-
butskristof
- Elite Poster
- Berichten: 1457
- Lid geworden op: 19 dec 2011, 18:42
- Locatie: Heist-op-den-Berg
- Uitgedeelde bedankjes: 483 keer
- Bedankt: 98 keer
- Contacteer:
Google ook eens op "knapsack problem", maar dat is in principe wel de oplossing dieje moet volgen dacht ik. Misschien dat je wel een kant-en-klaar script of zo tegenkomt.
-
meon
- Administrator
- Berichten: 16609
- Lid geworden op: 18 feb 2003, 22:02
- Twitter: meon
- Locatie: Bree
- Uitgedeelde bedankjes: 564 keer
- Bedankt: 759 keer
- Contacteer:
Yep, uw sectorgrootte/wijze van formatteren gaat mogelijk nog wel roet in het eten gooien van je algoritme...cloink schreef:Yep, bovenstaande manier (groot -> klein) zou prima moeten werken!
Let wel: zo zou het natuurlijk kunnen dat je bepaalde sticks hebt met een klein aantal grote files en dan enkele sticks met een belachelijke hoeveelheid aan kleine files, m.a.w. dat algoritme gaat niet echt netjes balanceren. Als je dat wil, zou je eerst onderverdelingen moeten maken (alle files tussen x en y, daarnaast alle files tussen y en z, enz. en dan bv. slechts max. X files uit de grootste nemen o.i.d.).
-
ubremoved_539
- Deel van't meubilair
- Berichten: 29849
- Lid geworden op: 28 okt 2003, 09:17
- Uitgedeelde bedankjes: 446 keer
- Bedankt: 1985 keer
Zolang hij z'n files laat afronden naar het eerst volgende veelvoud van de blocksize is het geen probleem.
Nu als alle sticks even groot zijn kan je misschien beter mutipart zippen.
Nu als alle sticks even groot zijn kan je misschien beter mutipart zippen.
