WinFuture-Forum.de: Such Algorithmus Für Kleinste Menge Von Zahlen - WinFuture-Forum.de

Zum Inhalt wechseln

Nachrichten zum Thema: Entwicklung
Seite 1 von 1

Such Algorithmus Für Kleinste Menge Von Zahlen


#1 Mitglied ist offline   Beisszeh 

  • Gruppe: Mitglieder
  • Beiträge: 1
  • Beigetreten: 08. Juli 07
  • Reputation: 0

geschrieben 08. Juli 2007 - 20:06

Hallo zusammen,

ich suche für folgendes Problem den passenden Algorithmus:

Es gibt eine Menge von Zahlen:
z.B.: 1000, 700, 300, 500, 70, 1500

ich suche jetzt eine Lösung, die mir aus der oben angegebenen Menge die kleinste Menge von Zahlen herraussucht, mit denen ich alle anderen Zahlen durch Addition darstellen kann. In diesem Fall:

700, 300, 500, 70

die 1000 lässt sich mit 700 + 300 darstellen und die 1500 mit 700+300+500.

Weiss da jemand rat?

Dieser Beitrag wurde von Beisszeh bearbeitet: 08. Juli 2007 - 20:06

0

Anzeige



#2 Mitglied ist offline   MNG 

  • Gruppe: aktive Mitglieder
  • Beiträge: 293
  • Beigetreten: 29. März 06
  • Reputation: 0

geschrieben 09. Juli 2007 - 19:55

Da sehe ich das berühmt-berüchtigte Knapsack-Problem (kann aufgefasst werden als Partitionierung einer Zahl durch die Summe einer Teilmenge von Zahlen einer gegebenen Menge) hervorblitzen. Lösen, wenn auch sehr ineffizient, lässt sich das mit dem Ansatz dynamischer Programmierung. Einen grob skizzierten Algorithmus findest du bei Wikipedia, den wirst du allerdings noch kräftig anpassen müssen:
http://de.wikipedia....Rucksackproblem
0

#3 _Fenix_

  • Gruppe: Gäste

geschrieben 11. Juli 2007 - 09:59

Willst du, dass die Zahlenmenge ohne Zurücklegen gebildet wird, oder mit Zurücklegen?
Also Ursprung:
1000, 500, 1500
Ergebnis mit Zurücklegen:
500 (500 + 500 = 1000, 500 + 500 + 500 = 1500)
Ergebnis ohne Zurücklegen:
500, 1000 (1000 = 1000, 1000 + 500 = 1500)
0

Thema verteilen:


Seite 1 von 1

1 Besucher lesen dieses Thema
Mitglieder: 0, Gäste: 1, unsichtbare Mitglieder: 0