[VB.NET] Efficient dozen met blokken vullen*

[ikkuhqhp]

hoi, ik ben een programma aan het maken dat groepen, het liefst zo effieciënt mogelijk, moet hergroeperen.

Casus: Ik heb een x hoeveelheid blokken. Ik heb dozen van 2000, 5000 en 10.000. Ik mag in totaal maar 15 dozen gebruiken. De hoeveelheid blokken verandert elke zoveel minuten. Dus op dat moment moet er weer gekeken worden of alles aangepast moet worden. Ik heb op het moment zoiets in mijn hoofd zitten:

Visual Basic:

Private Sub Blokken()
lbl begin
haal hier de hoeveelheid blokken op
if blokken >= 2000 then
doe 2000 blokken in 1 doos
goto: begin
elseIf dozenvan2000 >= 3 then
doe 3 dozen weg
doe blokken in doos van 5000
goto begin
elseif dozenvan5000 >= 2 then
doe 2 dozen van 5000 weg
doe blokken in doos van 10.000
end if
if dozenvan10.000 >= 15 then
doe ze in een truck en verzend ze
end if
MsgBox('Gestapeld!")
End Sub

Ik weet hoe ik de hoeveelheid dozen en blokken van alles op moet halen, ook hoe ik de blokken uit de ene doos moet gooien en in de andere moet doen. Het probleem zit hem dus in de efficiëntie van dit schema. Stel ik heb 4.000 blokken, dan doet hij 2 queries om ze in dozen te doen, vervolgens misschien nog eens om eentje van 5000 te nemen en dan eventueel nog om een van 10.000 te doen. Dat zijn een heleboel queries!
Verder weet ik niet eens hoe je de GOTO in VB.NET moet gebruiken.

Kortom, vragen, vragen en nog eens vragen.

Wie helpt mij?

ps. ik weet dat GOTO verwerpelijk is, maar dat lijkt hier toch wel te werken. Want hoe dan ook, dit zou goed moeten functioneren!

[Onbekend]

Je uitleg en je code lijken iets anders te doen.

Uit je uitleg begrijp ik het volgende:
Er zijn 3 maten dozen, en je mag zo min mogelijk dozen gebruiken.
De dozen moeten altijd compleet gevuld worden.

Dus als je 37.000 blokken hebt, heb je 3 dozen van 10.000 nodig, 1 doos van 5.000 en 1 doos van 2.000.


De code zou dan ongeveer zo moeten zijn:

Visual Basic:

Private Sub Blokken(ByVal AantalBlokken As Integer)
Dim AantalDozen10000 As Integer = 0
Dim AantalDozen5000 As Integer = 0
Dim AantalDozen2000 As Integer = 0

Do While AantalBlokken >= 10000
    AantalDozen10000 += 1
    AantalBlokken -= 10000
Loop

Do While AantalBlokken >= 5000
    AantalDozen5000 += 1
    AantalBlokken -= 5000
Loop

Do While AantalBlokken >= 2000
    AantalDozen2000 += 1
    AantalBlokken -= 2000
Loop

MsgBox("Klaar")
End Sub

[aOk]

Dit heet: Wikipedia: Knapsack problem

[Haan]

ikkuhqhp schreef op zondag 01 juni 2008 @ 12:34:


ps. ik weet dat GOTO verwerpelijk is, maar dat lijkt hier toch wel te werken. Want hoe dan ook, dit zou goed moeten functioneren!

Het feit dat het kán, betekent niet dat het ook goed is

[ikkuhqhp]

Onbekend schreef op zondag 01 juni 2008 @ 12:44:
Je uitleg en je code lijken iets anders te doen.

Uit je uitleg begrijp ik het volgende:
Er zijn 3 maten dozen, en je mag zo min mogelijk dozen gebruiken.
De dozen moeten altijd compleet gevuld worden.

Dus als je 37.000 blokken hebt, heb je 3 dozen van 10.000 nodig, 1 doos van 5.000 en 1 doos van 2.000.


De code zou dan ongeveer zo moeten zijn:

Visual Basic:

Private Sub Blokken(ByVal AantalBlokken As Integer)
Dim AantalDozen10000 As Integer = 0
Dim AantalDozen5000 As Integer = 0
Dim AantalDozen2000 As Integer = 0

Do While AantalBlokken >= 10000
    AantalDozen10000 += 1
    AantalBlokken -= 10000
Loop

Do While AantalBlokken >= 5000
    AantalDozen5000 += 1
    AantalBlokken -= 5000
Loop

Do While AantalBlokken >= 2000
    AantalDozen2000 += 1
    AantalBlokken -= 2000
Loop

MsgBox("Klaar")
End Sub

dankjewel, dat is het!

[apokalypse]

Waarom worden er while lussen gebruikt, terwijl je dit met een deling, en dan afronden (een floor), in 1 keer kan weten...?

[ValHallASW]

Tsja, je zult je probleemstelling toch iets beter moeten specificeren: wat is 'efficient'?

Casus: Ik heb een x hoeveelheid blokken. Ik heb dozen van 2000, 5000 en 10.000. Ik mag in totaal maar 15 dozen gebruiken.

Constraint = max 15 dozen
Oplossing: gebruik 15 dozen van 10.000 blokken

(net even met luite over gehad.. wat is efficient? minste loze ruimte? minste dozen? minste oppervlakte dozen? etc)

[ikkuhqhp]

effieciënt is hier "zo min mogelijk queries", ik wil de server niet te veel belasten namelijk

[ValHallASW]

Zo min mogelijk queries: alleen de grootste doos (10K dus) gebruiken en die een voor een vullen tot je er 15 hebt. Maar toch heb ik zo'n vermoeden dat dat niet is wat je wilt... want dat had je zelf ook wel kunnen bedenken. Formuleer je probleem nou eens wat beter

[Onbekend]

apokalypse schreef op zondag 01 juni 2008 @ 13:19:
Waarom worden er while lussen gebruikt, terwijl je dit met een deling, en dan afronden (een floor), in 1 keer kan weten...?

Floor is inderdaad ook een mogelijkheid, en zal zeker sneller werken als je nog meer dozen hebt.
Ik had maar even snel een voorbeeldje gemaakt....


Over de topictitel:
Goto's waren vroeger echt nodig omdat er met regelnummers werd gewerkt. Nu heb je procedures en functies welke je aan kan roepen.
Tegenwoordig is elke goto-opdracht te vervangen door een if-statement of een do-, while- of for-loop.

[ValHallASW]

Onbekend schreef op zondag 01 juni 2008 @ 20:44:
[...]
Tegenwoordig is elke goto-opdracht te vervangen door een if-statement of een do-, while- of for-loop.

Niet in alle talen. Er zijn maar een aantal talen waar je

C:

while (...) {
  while (...) {
    (...)
    if (...) {
      goto jump_from_loop
    }
    (...)
  }
}
jump_from_loop:
(ga verder)

hoewel dit ook met een functie kan. Als je dat niet wilt dan is dit in ieder geval beter dan

C:

while ((...) and not exit_from_loop) {
  while ((...) and not exit_from_loop) {
    (...)
    if (...) {
      exit_from_loop = 1;
    } else {
      (...)
    }
  }
  if (not exit_from_loop) {
    (...)
  }
}
(ga verder)

maar een break-met-naam, zoals in bv. java, is natuurlijk mooier. Kies wat het duidelijkste is, en dat kan soms best een goto zijn. (maargoed, zie bv [C#] Gebruik van goto uit den boze? voor die discussie)

[ Voor 7% gewijzigd door ValHallASW op 01-06-2008 21:53 ]

[fleppuhstein]

Onbekend schreef op zondag 01 juni 2008 @ 20:44:
[...]
Over de topictitel:
Goto's waren vroeger echt nodig omdat er met regelnummers werd gewerkt. Nu heb je procedures en functies welke je aan kan roepen.
Tegenwoordig is elke goto-opdracht te vervangen door een if-statement of een do-, while- of for-loop.

goto wordt nog regelmatig gebruikt in vb.net voor error afhandeling binnen een functie of procedure.

[Onbekend]

fleppuhstein schreef op zondag 01 juni 2008 @ 22:55:
[...]


goto wordt nog regelmatig gebruikt in vb.net voor error afhandeling binnen een functie of procedure.

Dan gebruik ik Exit Sub of Exit Function. Ik wil alleen zeggen dat er altijd een mogelijk is om de goto te vervangen voor iets anders.

[Bosmonster]

ValHallASW schreef op zondag 01 juni 2008 @ 15:24:
Zo min mogelijk queries: alleen de grootste doos (10K dus) gebruiken en die een voor een vullen tot je er 15 hebt. Maar toch heb ik zo'n vermoeden dat dat niet is wat je wilt... want dat had je zelf ook wel kunnen bedenken. Formuleer je probleem nou eens wat beter

Ben nog steeds benieuwd naar het antwoord. Kan me moeilijk voorstellen dat bij het berekenen van het aantal dozen de efficiency van de query de belangrijkste (of uberhaupt een belangrijke) requirement is namelijk

[Janoz]

aOk schreef op zondag 01 juni 2008 @ 12:51:
Dit heet: Wikipedia: Knapsack problem

Dit is niet het knapsack probleem. Bij het knapsack probleem heeft hetgeen dat in de dozen moet ook een wisselende afmeting. In dit geval is de oplossing niet npc, maar kan gewoon begonnen worden met zo veel mogelijk in een grote doos te stoppen.

Verder zie ik ten eerste niet echt in wat nu het probleem is en wat de topicstarter onder 'efficient' verstaat, en ten tweede wat dit uberhaupt met goto te maken heeft.

[PolarBear]

fleppuhstein schreef op zondag 01 juni 2008 @ 22:55:
[...]


goto wordt nog regelmatig gebruikt in vb.net voor error afhandeling binnen een functie of procedure.

Huh? Error handeling in VB.Net gaat toch gewoon met een Try Catch oplossing?

[Voutloos]

On Error Goto ... was ten tijde van VB <= 6 behoorlijk populair en is daarna bij te veel mensen blijven hangen. (en er zitten uberhaupt nog veel mensen op VB6 )

Maar goed, het echte probleem van dit topic is dat het een slecht gespecificeerde opdracht is. Er mist genoeg om nog niet over implementatie te moeten hebben, laat staan over implementatie middels allemaal slechte stijl hackwerk.

Het klinkt nu als zoveel mogelijk grote dozen gebruiken en het restant in de kleinst passende doos stoppen en mits de blokken allemaal dezelfde omvang hebben is het een te eenvoudige deling en ben je zelfs al stom bezig als je met loopjes aan komt zetten.

[ Voor 31% gewijzigd door Voutloos op 02-06-2008 09:38 ]

[MrSleeves]

apokalypse schreef op zondag 01 juni 2008 @ 13:19:
Waarom worden er while lussen gebruikt, terwijl je dit met een deling, en dan afronden (een floor), in 1 keer kan weten...?

Precies:
Private Function Blokken(ByVal AantalBlokken As Integer) as Integer
Dim AantalDozen10000 As Integer = 0
Dim AantalDozen5000 As Integer = 0
Dim AantalDozen2000 As Integer = 0

AantalDozen10000 = AantalBlokken MOD 10000
AantalBlokken -= AantalDozen10000 * 10000
AantalDozen5000 = AantalBlokken MOD 5000
AantalBlokken -= AantalDozen5000 * 5000
AantalDozen2000 = AantalBlokken MOD 2000
AantalBlokken -= AantalDozen2000 * 2000

return AantalBlokken
End Function

Geef je ook nog de resterende blokken terug.
Je moet ook nog wat pre en post-condities stellen/afvangen. Wat als er meer dan 150.000 blokken zijn? Dan heb je altijd meer dan 15 dozen.

[Voutloos]

MOD geeft toch echt de rest van deling terug. Dus gewoon deling en floor doen.

Maar kom op zeg, we hoeven hier toch niet een drietal groep 7 sommetjes voor te doen?

[MrSleeves]

Oeps... my bad..

Zat ik dus even totaal verkeerd om te denken

[ Voor 55% gewijzigd door MrSleeves op 02-06-2008 10:05 ]

[ikkuhqhp]

Wat ik vergeten was dat er ook zo min mogelijk vrij rondliggende blokken mogen zijn. Het zit zo: om de 5 minuten komt er een lading blokken binnen. Deze moeten zo veel mogelijk in dozen worden gestopt, waarbij het wél de voorkeur heeft om ipv 3 dozen van 2000, 1 doos van 5000 te hebben en 1000 "losse" blokken. Maar goed, ik ben eruit hoe ik het ga doen, ik heb het idee van "onbekend" geïmplementeerd!
ik dank u allen