Algorithmus gesucht

[Testa2014]

Hallo zusammen,

ich suche einen Algorithmus um folgenden Thema zu behandeln:

Als Ausgangslage habe ich eine unterschiedliche Anzahl von Objekten mit entsprechenden Punktzahlen.
Das Ziel ist diese Objekte in entsprechen Reihen effizient unterzubringen.
Jede Reihe hat 10 Punkte, wie diese gefüllt wird spielt keine Rolle.
Die Punktzahl innerhalb der Reihe darf auch mit dem Objekt überschritten werden (wenn vor der Füllung der Punktestand <10 ist).
-> Für die Befüllung ist immer der Punktestand vor dem einfügen relevant.

Ein kurzes Bsp.

Objekt	Punkte	Anzahl
1	3	5
2	8	2

Um dies in möglichst wenig Reihen unterzubringen würde es z.B. wie folgt ausschauen:
Reihe 1: 1 - 1 - 1 - 2 (3 + 3 + 3+ 8) - das Objekt 2 wird bei einem Punktestand von 9 hinzugefügt
Reihe 2: 1 - 1 - 2 (3 + 3 + 8)

Kein Sinn würde:
2 - 1
2 - 1
1 - 1 - 1
machen. Hier würden 3 Reihen benötigt werden.

Das ganze würde sich dann so weit spinnen lassen:

Kennt hierfür jemand einen Algorithmus?

Mein Ansatz wäre, ich nehme alle kleinen Punkte und summiere die bis zur 9, anschließend werden die großen Objekte hinzugefügt. Nur erscheint mir das ganze etwas "nicht zielführend". Und alles durchprobieren möchte ich auch gerne vermeiden.

Vielen Dank und einen schönen sonnigen Sonntag.
testa

 

[DieRenteEnte]

Auch wenn sich hier jemand finden wird der eine Lösung dafür hat, solltest du bei so speziellen Fragen eher in einem Mathematik Forum fragen.

https://duckduckgo.com/?q=mathematik+forum&t=lm&ia=web

Dort könnte man dir vielleicht noch bessere Lösungen vorschlagen.
Vielleicht sogar noch besser als es ein Programmierer tun würde, der schon oft Algorithmen erstellt hat.

 

[benneq]

Ist doch trivial:

Schritt 1: Suche die größte Zahl, die noch in die Reihe passt - 1 (in einer Schleife)
Schritt 2: Nimm die größte Zahl aus dem Pool
Schritt 3: Nächte Reihe

Am Beispiel erklärt:
Angenommen, du hast hast folgende Zahlen in deinem Pool: 1,1,2,4,5,5,8,9

Schritt 1: 9, weil 9 die größte Zahl ist, die noch in die Reihe passt - 1. (Die Reihe hat 10 Plätze frei, also suchen wir nach der größten Zahl < 10.)
Schritt 2: Größte Zahl aus dem Pool nehmen: 8
Schritt 3: Reihe voll: 9+8=17. Nächte Reihe
Schritt 1: 5 (Die Reihe hat 10 Plätze frei, also suchen wir nach der größten Zahl < 10.)
Schritt 1 (Schleife): 4 (Die Reihe hat 5 Plätze frei, also suchen wir nach der größten Zahl < 5.)
Schritt 2: 5
Schritt 3: Reihe voll: 5+4+5=14. Nächte Reihe
Schritt 1: 2 (Die Reihe hat 10 Plätze frei, also suchen wir nach der größten Zahl < 10.)
Schritt 1 (schleife): 1 (Die Reihe hat 8 Plätze frei, also suchen wir nach der größten Zahl < 8.)
Schritt 1 (schleife): 1 (Die Reihe hat 7 Plätze frei, also suchen wir nach der größten Zahl < 7.)
Schritt 2: Entfällt, weil keine Zahlen mehr übrig.
Schritt 3: Reihe voll: 2+1+1=4

Am einfachsten ist es, wenn du die Zahlen aus den Objekten extrahierst und in einer sortierte Liste packst und diese dann von Groß nach Klein abarbeitest.

 

[new Account()]

Für hohe Platzeffizienz wirst du nicht ums rumprobieren kommen.
Soweit ich verstanden habe, dürfte das bin packing Problem Recht ähnlich zu deinem Problem sein, was es inherent schwierig zu berechnen macht: https://en.m.wikipedia.org/wiki/Bin_packing_problem

 

[kuddlmuddl]

Das ist ne Abwandlung vom Rucksackproblem. Der Unterschied ist, dass man dort exakt treffen muss. Ich glaube nicht, dass es dadurch einfacher wird. Das Rucksackproblem ist ein Beispiel woran man heute festmacht P != NP zu vermuten.
@benneque Algos die eine Lösung finden sind selbstgänger. Die große Frage ist, ob man einen Algo findet, der nicht exponentielle Komplexität hat, wie zB Bruteforce, um die optimale Lösung zu finden.
@Highspeed Opi Ein Mathe-Forum ist natürlich nie verkehrt aber im Mathestudium kommt P!=NP nicht unbedingt vor aber in jedem Informatik-Studium auf jeden Fall. Programmieren finde ich daher nicht verkehrt. Mathematiker sind imho generell nicht unbedingt die Experten für Algos, weil sie ja oft nach einem Existenz-Beweis für irgendetwas schon zufrieden sind

"Und alles durchprobieren möchte ich auch gerne vermeiden."
https://en.wikipedia.org/wiki/Knapsack_problem#Solving

 

[benneq]

Er wollte EINEN Algorithmus. Meiner funktioniert und ist sogar ziemlich effizient, wenn man seinen Zahlenpool vorher sortiert. Zumindest kann ich mir gerade nichts vorstellen, was weniger Komplexität beinhaltet.

 

[new Account()]

Sicher, dass er optimal ist?

 

[RalphS]

Das ist nicht wie, sondern relativ exakt das Knapsackproblem. Vermutlich eine Hausaufgabe.

Effizient zu lösen geht das nur, wenn man ein Genie ist und P id NP nachweisen kann. Alle anderen müssen Bruteforcen, also einfach alle Kombinationen durchprobieren.

Und die sind n! komplex.

 

[Testa2014]

Hallo zusammen,

da hat sich ja einiges angestaut.

ISchritt 1: Suche die größte Zahl, die noch in die Reihe passt - 1 (in einer Schleife)
Schritt 2: Nimm die größte Zahl aus dem Pool
Schritt 3: Nächte Reihe

Wenn ich hier als Bsp. den Excel Ausschnitt nehme, würde ich 10 Reihen benötigen. Also 2 zu viel, der Ansatz ist schon mal gut. Hab mich auf Klein und dann groß versteift.

Soweit ich verstanden habe, dürfte das bin packing Problem Recht ähnlich zu deinem Problem sein, was es inherent schwierig zu berechnen macht: https://en.m.wikipedia.org/wiki/Bin_packing_problem

Sortiere die Objekte nach absteigendem Gewicht
Füge die Objekte der Reihe nach ein,
sodass jedes in den ersten Behälter gegeben wird, in dem noch genug Platz ist.
Falls in keinem der bereits geöffneten Behälter genügend Platz ist, öffne einen neuen.

ein wenig gedreht könnte es klappen .... muss ich nachher mal ausprobieren. Danke für den Ansatz.

Das ist ne Abwandlung vom Rucksackproblem.

Das triffts doch fast noch besser, probier ich nachher auch mal aus.

Vermutlich eine Hausaufgabe.

Zum Glück bin aus dieser Zeit schon raus. Ist ein kleines Projekt um ein paar Leuten etwas arbeit abzunehmen.

Viele Grüße
testa

 

[floTTes]

Effizient zu lösen geht das nur, wenn man ein Genie ist und P id NP nachweisen kann. Alle anderen müssen Bruteforcen, also einfach alle Kombinationen durchprobieren.

Vielleicht findet der Dude in NUMB3RS das doch noch raus!