Springen naar inhoud

Algoritme (?) opstellen


  • Log in om te kunnen reageren

#1

Jeroen Noten

    Jeroen Noten


  • 0 - 25 berichten
  • 3 berichten
  • Gebruiker

Geplaatst op 01 mei 2008 - 21:57

Hallo,
Ik ben bezig met programmeren en nu zit ik met een probleem. Omdat deze (volgens mij) meer met wiskunde dan met programmeren te maken heeft heb ik hem maar hier geplaatst. Ik zal het probleem beschrijven. Het gaat om een donatiesysteem via sms, maar de context is denk ik niet zo van belang.

Het probleem:
Er zijn vier vaste getallen: 40, 90, 110 en 150
Er is ook nog een door een gebruiker ingevoerd getal X. Dit is een heel getal (geen kommagetal of een breuk) en is 0 of hoger.
Nu moet er een combinatie van die 4 getallen worden gezocht en als uitkomst moet er ůf X uitkomen ůf een zo dicht mogelijk getal bij X, maar het mag er niet onder liggen. Daarnaast is er ook nog de voorwaarde dat de getallen zo groot mogelijk moeten zijn (dus niet 40 en 110, maar 150).

Voorbeelden:
een gebruiker geeft 310 in, dan moet eruit komen: 110, 110 en 90
een gebruiker geeft 272 in, dan moet eruit komen: 90 en 90

Volgens mij moet ik hiervoor dus een algoritme opstellen en die vervolgens omzetten in programmercode (JavaScript in dit geval). Een algoritme omzetten in programmercode lukt me wel, maar het opstellen van het algoritme lukt me niet, ik heb al een tijd geprobeerd, maar ik krijg er niet het goede uit. Kan iemand me helpen?

Veranderd door Jeroen Noten, 01 mei 2008 - 21:58


Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 02 mei 2008 - 06:36

Kan iemand me helpen?

Laat zien wat je al hebt dan kunnen wij je vertellen of je op de goede weg zit.

#3

Fred F.

    Fred F.


  • >1k berichten
  • 4168 berichten
  • Pluimdrager

Geplaatst op 02 mei 2008 - 13:18

Nu moet er een combinatie van die 4 getallen worden gezocht en als uitkomst moet er ůf X uitkomen ůf een zo dicht mogelijk getal bij X, maar het mag er niet onder liggen.

Ik denk dat je bedoelt: het mag er niet boven liggen.

een gebruiker geeft 272 in, dan moet eruit komen: 90 en 90

Bedoel je 90 en 90 en 90 ?

Dit soort problemen is eenvoudig op te lossen met Integer Programming, een vorm van Linear Programming, maar dat is niet iets wat je even zelf programmeert.

Het doet mij ook denken aan het zogenaamde Knapsack problem, of aan Bin Packing.

In al die gevallen is de opgave om zoveel mogelijk voorwerpen (in jouw geval de getallen 40, 90, 110 en 150) in een bepaal volume (de door jouw gebruiker ingevoerde waarde voor X) te pakken.

Gebruik ook de zoekfunctie (rechtsboven) van dit forum want het staat me bij dat beide termen al eens eerder besproken zijn.
Hydrogen economy is a Hype.

#4

Jeroen Noten

    Jeroen Noten


  • 0 - 25 berichten
  • 3 berichten
  • Gebruiker

Geplaatst op 02 mei 2008 - 14:26

Laat zien wat je al hebt dan kunnen wij je vertellen of je op de goede weg zit.

Ja ik had dit, maar hij werkt niet goed:

var smsamounts = [150, 110, 90, 40];var smscredit = X;var smsnum = {};for (var i = 0; i < smsamounts.length; i++) {	smsnum[smsamounts[i]] = Math.floor(smscredit / smsamounts[i]);	smscredit -= smsnum[smsamounts[i]] * smsamounts[i];}


In de variabele smsnum komt dan het aantal van elk getal te staan. Maar als ik nu X = 310 invoer, dan komt eruit:
smsnum = {	150: 2,	110: 0,	90: 0,	40: 0}
maar er zou uit moeten komen:
smsnum = {	150: 0,	110: 2,	90: 1,	40: 0}

Ik denk dat je bedoelt: het mag er niet boven liggen.

Nee, de som van de getallen die eruit komen moet minimaal X zijn, maar het moet er zo min mogelijk boven liggen.

Bedoel je 90 en 90 en 90 ?

Oh het tweede voorbeeld is inderdaad fout :D

Het moet zijn:

een gebruiker geeft 272 in, dan moet eruit komen: 150, 90 en 40

Dit soort problemen is eenvoudig op te lossen met Integer Programming, een vorm van Linear Programming, maar dat is niet iets wat je even zelf programmeert.

Het doet mij ook denken aan het zogenaamde Knapsack problem, of aan Bin Packing.

In al die gevallen is de opgave om zoveel mogelijk voorwerpen (in jouw geval de getallen 40, 90, 110 en 150) in een bepaal volume (de door jouw gebruiker ingevoerde waarde voor X) te pakken.

Gebruik ook de zoekfunctie (rechtsboven) van dit forum want het staat me bij dat beide termen al eens eerder besproken zijn.

Bedankt voor de hulp, ik ga eens kijken!

#5

Fred F.

    Fred F.


  • >1k berichten
  • 4168 berichten
  • Pluimdrager

Geplaatst op 02 mei 2008 - 14:54

Omdat je nu zegt dat de som der getallen wel degelijk groter of gelijk aan X moet zijn (wat eerst niet bleek uit je tweede voorbeeld) is het Knapsack of Bin-packing probleem niet meer als zodanig van toepassing.

Wel kun je wellicht de methodiek van deze algoritmes aanpassen voor jouw situatie. Het gaat er immers om om het verschil tussen X en Som zo klein mogelijk te maken, alleen is bij jou het te minimaliseren verschil gelijk aan Som - X in plaats van X - Som.
Hydrogen economy is a Hype.

#6

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 02 mei 2008 - 16:10

pseudocode:
initialiseer 'min' en 'aantal in min'.
for a = 0 to ceiling(x/40) {
  for b = 0 to celing(x/90) {
	for c = 0 to ceiling(x/110) {
	  for d = 0 to celing(x/150) {
		diff = a*40 + b*90 + c*110 + d*150 - x;
		if (diff >= 0) {
		  if (diff < min) or ((diff == min) and (aantal in min) < (a+b+c+d)) {
			bewaar gegevens a,b,c,d;
			min = diff;
			aantal in min = a + b + c + d;
		  }
		}
	  }
	}
  }
}

Kijk eens of je hier iets mee kan.

#7

Jeroen Noten

    Jeroen Noten


  • 0 - 25 berichten
  • 3 berichten
  • Gebruiker

Geplaatst op 03 mei 2008 - 12:49

Ja dankje! Het werkt!
Alleen nog 1 aanpassing:
(aantal in min) > (a+b+c+d)
Want er moet juist een zo klein mogelijk aantal getallen uitkomen. Dus alleen doorlaten als het vorige aantal groter is dan het huidige.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures