Laden...

Wie löse ich das Rucksack Problem mit mehreren Rucksäcken?

Erstellt von OXO vor 3 Jahren Letzter Beitrag vor 3 Jahren 1.821 Views
O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren
Wie löse ich das Rucksack Problem mit mehreren Rucksäcken?

Hallo Leute,

versuche gerade eine eigene Listen-Implementierung einer sortierten und limitierten Liste zu machen. Habe versucht, von einer List<T> abzuleiten. Da kann ich aber die Add-Methode gar nicht überschreiben, sondern nur überlagern mit new Add(T item). Das Interface IList<T> mit allen Implementierungen zu implementieren scheint mir auch komisch und too much.

Im Grunde wollte ich in einer Add(T item)-Methode eine Prüfung implementieren, die prüft, wo ein T sortiert einzufügen ist, damit die Liste immer sortiert bleibt. Gleichzeitig wollte ich darin darauf achten, dass die Liste eine initial festgelegte Kapazität nicht überschreitet (z.B. Begrenzung auf 10 Elemente).

Über die Collection<T> wollte ich nicht gehen, da ich hier nur eine Insert-Methode mit zusätzlichem Index überschreiben kann. Eine ArrayList<T>-Ableitung funktioniert auch nicht und bei einer ArrayList-Ableitung bietet es mir nur eine Implementierung von Add(object value) zum Überschreiben an, also nicht Add(T item), was für den Anwender der Liste schon schön wäre.

Wie muss ich das denn richtig machen, um bei meiner Listen-Implementierung wirklich am Ende etwas, wie Add(T item) zur Verfügung zu haben und warum geht das denn nicht über eine List<T>-Ableitung?

C
2.121 Beiträge seit 2010
vor 3 Jahren

Ich weiß nicht was du mit überlagern meinst, aber die Ableitung einer Liste sollte all das erlauben was du tun willst.
Was genau geht denn wie nicht?

2.078 Beiträge seit 2012
vor 3 Jahren

Das Interface IList<T> mit allen Implementierungen zu implementieren scheint mir auch komisch und too much.

Warum? Für sowas gibt es doch Interfaces.

Wenn Du Faul bist, dann schreib eine Variable mit dem selben List-Typ in die Klasse und aktuelle VisualStudios können dir das Interface dann automatisch anhand dieser Variable implementieren.
Dann musst Du nur noch anpassen.

Alternativ gibt's noch die Collection<T>-Klasse, die ist als Basisklasse für Listen gedacht und bietet auch entsprechende virtuelle Methoden an.

T
2.219 Beiträge seit 2008
vor 3 Jahren

Interfaces sind genau für diesen Fall gedacht, hier wäre eine Implementierung von IList<T> sogar am sinnvollsten.
Hier könntest du dann auch eine Container Klasse umsetzen, die intern z.B. auf der List<T> als Datenspeichr aufbaut.
Die entsprechenden Methoden kannst du dann an die Aufrufe der List<T> weiterleiten.

Alternativ wäre zu prüfen ob du nicht gleich auf SortedList<TKey, TValue> aufbaust, dann musst du dich nicht um die Einfügung an derrichtigen Stelle kümmern.
Nur die Größe der Liste müsstest du dann noch selbst verwalten.

Vielleicht wäre aber auch etwas Hintergrundwissen nicht schlecht um dir eine bessere Alternative zu bieten.

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

16.806 Beiträge seit 2008
vor 3 Jahren

Die Limitierung und Co ist alles einfach mit einer eigenen Add-Implementierung von List zu lösen;

public new void Add(T entity)
{
   // if .. exception
   base.Add(entity)
}

Die Sortierung ist hier nicht so einfach bzw. relativ teuer im Sinne der benötigen Ressourcen; da wäre dann auch die Frage, ob man das wirklich braucht.

public new void Add(T entity)
{
   // if ..  exception
   base.Add(entity) 

   base.Sort();
}

Oft ist der Wunsch an eine immer-sortierte Liste premature optimization; es gibt sehr wenig Fälle, bei denen das wirklich sinnvoll ist. Ansonsten ist der reaktive Weg der Sortierung - also beim Lesen - meist der effizientere Weg.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Die Liste soll Elemente vom Typ MyData verwalten und auf x Elemente begrenzt sein.

Welche Elemente in die Liste kommen, ist von dem Wert der MyData.ErrorValue-Property abhängig (nach der wird dem wird die Liste sortiert). Das ständige Sortieren ist praktisch nur Mittel zum Zweck, um zu erkennen, welche Elemente noch in der Liste verbleiben dürfen.


class MyData : IEquatable<MyData>, IComparable<MyData>
{
     readonly int[] optimalRatios;

     public MyData(int numOptimalRatios)
     {
         this.optimalRatios= new int[numOptimalRatios];
     }
        
     public int[] OptimalRatios { get => this.optimalRatios; }
     public double ErrorValue { get; set; }

     public double Value1 { get; set; }
     public double Value2 { get; set; }
     public double Value3 { get; set; }

     public override string ToString()
     {
         return $"ErrorValue: {ErrorValue}; Value 1: {Value1}, Value 2: {Value2}, Value 3: {Value3}";
     }

     public int CompareTo(MyData other)
     {
         // A null value means that this object is greater.
         if (other == null)
             return 1;
          else
              return this.ErrorValue.CompareTo(other.ErrorValue);
     }

     public override int GetHashCode()
     {
         return this.ToString().GetHashCode();
     }

     public override bool Equals(object obj)
     {
         if (obj == null)
             return false;

         MyData objAsMyData = obj as MyData;
         if (objAsMyData == null)
             return false;
         
         return Equals(objAsMyData);
     }

     public bool Equals(MyData other)
     {
         if (other == null)
             return false;

         return (other.ErrorValue == this.ErrorValue) && 
                (other.Value1 == this.Value1) && 
                (other.Value2 == this.Value2) && 
                (other.Value3 == this.Value3);
     }
}


class LimitedSortedList : IList<MyData>
{
	private readonly IList<MyData> limitedList = new List<MyData>();
	
	public LimitedSortedList(int capacity)
	{
		this.Capacity = capacity;
	}



	public int Capacity { get; private set; }

	public MyData this[int index] { get => throw new System.NotImplementedException(); set => throw new System.NotImplementedException(); }

	public int Count => limitedList.Count;

	public bool IsReadOnly => limitedList.IsReadOnly;

	public void Add(MyData item)
	{
		int positionToInsert = limitedList.Count;
		for (int i = 0; i < limitedList.Count; i++)
		{
			if (item.CompareTo(limitedList[i]) < 0)
			{
				positionToInsert = i;
				break;
			}
		}

		limitedList.Insert(positionToInsert, item);
			
		if (limitedList.Count > this.Capacity)
			limitedList.RemoveAt(limitedList.Count - 1);
	}

	public void Clear()
	{
		limitedList.Clear();
	}

	public bool Contains(MyData item)
	{
		return limitedList.Contains(item);
	}

	public void CopyTo(MyData[] array, int arrayIndex)
	{
		throw new System.NotImplementedException();
	}

	public IEnumerator<MyData> GetEnumerator()
	{
		return limitedList.GetEnumerator();
	}

	public int IndexOf(MyData item)
	{
		return limitedList.IndexOf(item);
	}

	public void Insert(int index, MyData item)
	{
		throw new System.NotImplementedException();
	}

	public bool Remove(MyData item)
	{
		return limitedList.Remove(item);
	}

	public void RemoveAt(int index)
	{
		limitedList.RemoveAt(index);
	}

	IEnumerator IEnumerable.GetEnumerator()
	{
		return limitedList.GetEnumerator();
	}
}

Also z.B. Liste begrenzt auf 5 MyData-Elemente, deren ErrorValue mit Sortierung wie folgt ist {1.2, 5.3, 6.2, 8.1, 9.3 }

Ein neues MyData-Element mit ErrorValue = 5.3 in die Liste. In diesem Fall würde das Element mit dem Wert 9.3 raus fliegen {1.2, 5.3, 5.3, 6.2, 8.1 }

Meinst Du, dass eine Implementierung nach InsertSort mit nur 1 Element von der Performance her vorteilhafter ist, als wenn man es simpel macht und in der Add-Methode immer erst einmal das Element hinzufügt, dann sortiert über List<T>.Sort(...) und dann das letzte Element löscht, wenn die maximal erlaubte Kapazität überschritten ist?

Könnte man das wie oben mit der Daten-Klasse und Equals und GetHashCode auch so machen?

T
2.219 Beiträge seit 2008
vor 3 Jahren

Deine Frage kann man immer mit Ja beantworten, kannst du so implementieren.
Die Umsetzung ist aber, wie Abt auch schon schreibt, dann nur teuer durch die Sortierung bei jedem Insert.
Ebenfalls solltest du dann auch beachten, wenn AddRange verwendet wird, dass du dort dann

Ebenfalls hast du durch hinzufügen über die Kapazität hinaus dann auch das Problem, dass die List<T> beim ersten Überschreiten der vorgegebenen Größe dann das interne Array vergrößern + umkopieren muss.
Aktuell fehlt auch ein AddRange, was bei größeren Add Operationen z.B. durch eine andere Liste dazu führen würde dass du die Elemente einzeln hinzufügen und jedes mal die komplette Liste sortieren musst.
Dies wäre eine totaler Overkill an Rechenlast bei großen Listen.

Nachtrag:
Bei der aktuellen Implementierung zeigen sich auch schon erste Schwächen der Implementierung.

1.Warum soll der [] Index Operator bei Get und Set eine Exception werfen?
Dadurch kannst du keine gezielten Elemente abfragen, was aber nötig wäre wenn du z.B. auf ein bestimmtes Element zugreifen willst!
Hier würde ich direkt an den Index Operator der Liste zugreifen für Get.
Bei Set hingegen würde ich entweder eine Exception werden oder den setter leer Implenentieren, also ohne Funktion.

2.Ebenfalls wirft CopyTo eine Exception, was unnötig ist.
Die Daten kannst du per CopyTo ohne Probleme kopieren lassen, wenn es welche gibt.
Hier kannst du eigentlich die Methode deiner Liste aufrufen lassen.

3.Bei Insert macht die Exception schon Sinn, könnte man aber auch als leere Operation implementieren wenn nur du diese Klasse verwendest.

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Hallo T-Virus,

zunächst einmal vielen Dank für Deine Antwort und die Mühe!

Deine Frage kann man immer mit Ja beantworten, kannst du so implementieren.
Die Umsetzung ist aber, wie Abt auch schon schreibt, dann nur teuer durch die Sortierung bei jedem Insert.
Ebenfalls solltest du dann auch beachten, wenn AddRange verwendet wird, dass du dort dann

Was wolltest Du hier noch schreiben?

Ebenfalls hast du durch hinzufügen über die Kapazität hinaus dann auch das Problem, dass die List<T> beim ersten Überschreiten der vorgegebenen Größe dann das interne Array vergrößern + umkopieren muss.

Aktuell hab ich die maximale Kapazität erst einmal nur über meine interne Grenze festgelegt und verwende die normale List-Implementierung intern.

Aktuell fehlt auch ein AddRange, was bei größeren Add Operationen z.B. durch eine andere Liste dazu führen würde dass du die Elemente einzeln hinzufügen und jedes mal die komplette Liste sortieren musst.
Dies wäre eine totaler Overkill an Rechenlast bei großen Listen.

Da hast Du Recht! An ein AddRange hab ich zunächst einmal gar nicht gedacht und könnte ich noch einbauen

Nachtrag:
Bei der aktuellen Implementierung zeigen sich auch schon erste Schwächen der Implementierung.

1.Warum soll der [] Index Operator bei Get und Set eine Exception werfen?
Dadurch kannst du keine gezielten Elemente abfragen, was aber nötig wäre wenn du z.B. auf ein bestimmtes Element zugreifen willst!
Hier würde ich direkt an den Index Operator der Liste zugreifen für Get.
Bei Set hingegen würde ich entweder eine Exception werden oder den setter leer Implenentieren, also ohne Funktion.

Das war eigentlich blöd, da ich das nur mal so runter implementiert hab. Da gebe ich Dir vollkommen Recht auch, das muss ich nochmal nacharbeiten. Denn diese Funktionalität muss schon her

Was wäre beim Setter für den Anwender vorteilhafter? In der MSDN findet man oft auch Hinweise auf Exceptions, die bei der ein oder anderen Funktion geworfen werden. Ein richtiger Freund bin ich aber hier auch nicht davon. Ein Einfügen an einem bestimmten Index macht aber so natürlich auch nicht wirklich Sinn. Und ein "Einfügen am Index" mit einem Element, was wegen der Begrenzung auf x Elemente auch nie in der Liste ankommt, wenn es wegen der Sortierung raus fliegen würde, ist irgendwie auch komisch. Ansonsten hätte ich gesagt, gut, das Insert könnte auch über das normale Add(...) geschleust werden. Aber das ist wirklich seltsam als Anwender dann. Vermutlich dann doch noch das kleinste Übel mit der Exception

2.Ebenfalls wirft CopyTo eine Exception, was unnötig ist.
Die Daten kannst du per CopyTo ohne Probleme kopieren lassen, wenn es welche gibt.
Hier kannst du eigentlich die Methode deiner Liste aufrufen lassen.

Richtig, die könnte ich auch noch entsprechend implementieren

3.Bei Insert macht die Exception schon Sinn, könnte man aber auch als leere Operation implementieren wenn nur du diese Klasse verwendest.

Ist immer die Frage, was ist für den Anwender besser. Meine Vorgehensweise ist meistens, dass ich versuche so wenig wie möglich Exceptions zu werfen (was man mit meiner obigen Implementierung nicht meinen würde). Vielleicht eine leere Implementierung doch irgendwie sympatischer.

16.806 Beiträge seit 2008
vor 3 Jahren

Ist immer die Frage, was ist für den Anwender besser.

Die Frage ist immer noch, was Du eigentlich vor hast.
Siehe mein Beitrag oben, den Du offenbar etwas ignoriert hast 😉

Meine Vorgehensweise ist meistens, dass ich versuche so wenig wie möglich Exceptions zu werfen (was man mit meiner obigen Implementierung nicht meinen würde).

Das ist die teuerste Art und Weise in .NET mit Fehlern umzugehen.
Excptions sollten nur dann geworfen werden, wenn es wirklich notwendig ist; nicht um Logik zu steuern.
Steht auch in den .NET Design Guidelines. Daher widerspreche ich auch, dass eine Exception hier sinn macht, wenn es um die Logiksteuerung geht (was hier der Fall wäre).

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Ist immer die Frage, was ist für den Anwender besser.

Die Frage ist immer noch, was Du eigentlich vor hast.
Siehe mein Beitrag oben, den Du offenbar etwas ignoriert hast 😉

Tut mir leid, das war keine Absicht.

Im Grunde ist es nur, dass man eine Liste hat, die auf x Elemente begrenzt ist und bei der neue Elemente nur aufgenommen werden, wenn sie nicht größer sind, als das größte Element.

Es werden irgendwo im Programm Fehlerwerte berechnet und diese sollen natürlich möglichst gering sein. Angezeigt haben, möchte ich die besten x Ergebnisse mit den geringsten Fehlerwerten.

Die Sortierung dieser LimitedSortedList ist hier an sich nur Mittel zum Zweck, um zu sehen, welches Element raus fliegt, um Platz für einen noch kleineren Wert zu machen.

2.078 Beiträge seit 2012
vor 3 Jahren

Warum sortierst und limitierst nicht nur beim Anzeigen?

Das wäre insgesamt das gleiche Ergebnis, nur im ein vielfaches Einfacher.
LINQ bietet dafür schon alles nötige an, das wären dann OrderBy() und Take() oder Skip().

Alternativ gibt's noch die SortedList, allerdings arbeitet die mit Key-Value-Paaren.
Das kann aber auch wieder von Vorteil sein, da Du so leichter mehr Daten pro Eintrag speichern kannst.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Warum sortierst und limitierst nicht nur beim Anzeigen?

Hab nicht so weit ausgeholt, aber das Limitieren hat Gründe wegen dem Speicher.

Die Berechnungen ergeben so viele Daten, dass mein Programm irgendwann wegen nicht genügend Speicher weg krachen würde. Wollte mit dieser Liste dann das Problem mit der Limitierung umschiffen. Ansonsten würde es auch gehen.

16.806 Beiträge seit 2008
vor 3 Jahren

Berechnungen möchte man ja heutzutage so parallel wie möglich umsetzen, um die Ressourcen einer Maschine ausnutzen zu können.
Mit solch einer Liste schaffst Du Dir aber im Prinzip einen künstlichen Flaschenhals, wenn Du schreibend drauf zugreifen musst; ist es Dir das wert?

Aber die simpelste Implementierung (ohne die Beachtung der Performance) ist ja einfach nur ein Wrapper.

public class MyLimitedList<T> : IEnumerable<T>
{
    private readonly List<T> _list;

    public MyLimitedList(int size)
    {
        _list = new List<T>(size + 1);
    }

    public void Add(T e)
    {
        _list.Add(e);
        _list.Sort();

        if (_list.Capacity == _list.Count)
        {
            _list.RemoveAt(_list.Count - 1);
        }
    }

    public IEnumerator<T> GetEnumerator() => _list.GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
5.299 Beiträge seit 2008
vor 3 Jahren

System.Collections.ObjectModel.Collection<T> ist dafür vorgesehen.
Eigene Auflistungen zu basteln, und ist dafür ausgezeichnet geeignet.
Bestimmte Member sind protected virtual, sodass man mit Leichtigkeit gezielt das Verhalten modifizieren kann.
nämlich nur protected SetItem() und InsertItem() wären zu überschreiben - feddich.
So erbt man das komplette IList<T>-Interface, ohne auch nur einen Finger dafür zu rühren.

Wenn man auf Performance abzielt könnte man beim Einfügen sogar BinarySearch zum Auffinden der Einfüge-Position anwenden. Dazu einfach die innere Liste nehmen - das ist eine List<T>, und List<T> kann BinarySearch.
Dann muss beim Add nicht mehr sortiert werden. Nicht viel Aufwand, aber bei 10 Elementen scheint mir auch das unsinnig.

Der frühe Apfel fängt den Wurm.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Wenn man auf Performance abzielt könnte man beim Einfügen sogar BinarySearch zum Auffinden der Einfüge-Position anwenden. Dazu einfach die innere Liste nehmen - das ist eine List<T>, und List<T> kann BinarySearch.
Dann muss beim Add nicht mehr sortiert werden. Nicht viel Aufwand, aber bei 10 Elementen scheint mir auch das unsinnig.

Wie würde man mit BinarySearch eine Einfüge-Position ermitteln können? Ich dachte, so finde ich nur die Position eines vorhandenen Elementes.

In der Zwischenzeit blockiert mich tatsächlich aber auch die Parallelität, wie

schon erwähnt hatte.

Ich habe etwas am übergeordneten Algorithmus mit Parallel.For(...) experimentiert und wie schon erwähnt wurde, ist ein exklusives Einfügen hier nun mein Flaschenhals.

Am Einfachsten wäre es natürlich, wenn ich all meine berechneten Ergebnisse einfach mit nem simplen Add(...) der Liste hinzufügen könnte. Aber da läuft mir dann der Speicher über, da es einfach eine zu große Datenmenge ist.

Heißt, ich müsste ab und an schauen, dass ich eine Sortier-Aktion mit Dezimierung auf x Elemente einbaue, aber parallel ist das auch schon wieder so ein Kraftakt, der nicht klappen will.

4.931 Beiträge seit 2008
vor 3 Jahren

Wenn du in der Liste sowieso nur die x kleinsten Werte haben willst, warum fügst du dann größere Werte überhaupt hinzu?

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Wenn du in der Liste sowieso nur die x kleinsten Werte haben willst, warum fügst du dann größere Werte überhaupt hinzu?

Ich weiß doch gar nicht, welche Werte sich darin befinden !?!?

5.299 Beiträge seit 2008
vor 3 Jahren

Wie würde man mit BinarySearch eine Einfüge-Position ermitteln können? Ich dachte, so finde ich nur die Position eines vorhandenen Elementes. Tja, so kann man sich irren.
Ich hab dir doch gesagt, dass List<T> BinarSearch kann.
wie das geht, habich damals auch im Internet rausgefunden. Und dort gelernt, dass bei nicht-Match das Bit-Complement der EinfügePosition returnt wird.

aber wie gesagt: Wenn du wirklich mit nur 10 Elementen unterwegs bist (oder 100, oder 1000), dann lass den Quatsch, und insbesondere iwelche Parallelitäts-Experimente.

schnapp dir Collection<T> und bau erstmal eine funktionierende LimitedSortedList<T>.
Optimieren soll man immer!! als allerletztes machen.

Der frühe Apfel fängt den Wurm.

16.806 Beiträge seit 2008
vor 3 Jahren

Ich kann da ErfinderDesRades nur zustimmen.

Auch macht in meinen Augen ein "Experiment" wenig sinn, wenn man die Grundzüge hier gar nicht verstanden hat.

Aber da läuft mir dann der Speicher über, da es einfach eine zu große Datenmenge ist.

Ich vermute hier immer noch, dass dann einfach die Basis für die Verarbeitung nicht stimmt, wenn Du versuchst die Symptome mit einer Flaschenhals-Liste zu lösen.
Denke der Fisch stinkt an anderer Stelle.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Puh, also dann sprenge ich mal den Rahmen hier:

Die Aufgabe ist ein Optimierungs-Problem, bei dem die x besten Lösungen angezeigt werden können sollen.

Ich habe 3 Töpfe, die jeweils ein vorgegebenes Budget haben, z.B. 40 / 20 / 45
Dann gibt es n verschiedene Elemente, die frei ausgewählt werden können und Mengen von x bis y haben können. Zu jedem Element gibt es einen Vektor v, der den jeweiligen Anteil an den 3 Töpfen bei der Menge 1 beinhaltet.

Der Algorithmus soll nun die optimalen Mengen für jedes der n Element finden und zwar so, dass diese Daten im Vektor multipliziert mit der Menge am Ende die 3 Töpfe möglichst optimal ausfüllt. Natürlich darf kein Topf überlaufen. Am Ende könnten folgende Mengen als optimal raus kommen z.B. Element 1: 10, Elment 2: 12, ... Element n: 3

Ich berechne Kombinationsmöglichkeiten mit den verschiedenen Mengen und zu jeder einen Fehlerwert, der praktisch der Abstand zur optimalen Befüllung aller Töpfe ist. Je kleiner der Abstand, desto besser ist diese Mengen-Kombination (also z.B. Element 1: 10, Elment 2: 12, ... Element n: 3 -> ergibt Fehlerwert 0.12)

Die Errechneten Fehlerwerte mit den jeweiligen Mengen, werden dann in meiner LimitedSortedList gespeichert. Die Liste soll z.B. auf 5 Einträge beschränkt sein und nur die Mengen anzeigen, die den kleinsten Fehlerwert haben. Sprich, für die Anzeige, die 5 besten Mengen-Kombinationen.

Die Experimente mit der Parallelität sind gerade etwas aus Verzweiflung. Als Input hab ich mal angefangen für jedes Element 1 ... n eine Matrix mit den Werten zu erstellen, die von der Mindestmenge bis zur Höchstmenge eines Elementes läuft (bei jedem Elemente 1 .. n kann man noch definieren, was die Mindestmenge und was die Höchstmenge sein soll).
Dann hab ich mal gestartet und jede Kombinationsmöglichkeit der Matrizen ausgerechnet, dazu den Fehlerwert und dabei schon mal drauf geachtet, dass ich an der Höchstgrenze der Töpfe halt mache.

Trotzdem purzeln logischerweise sehr sehr viele Werte dabei raus und ich will aber ja nur 5 davon haben mit dem besten Fehlerwerten. Parallelität deshalb, weil logischweise so eine Berechnung davon profitieren kann. Schlecht, weil meine LimitedSortedList so natürlich nicht zurecht kommt.

16.806 Beiträge seit 2008
vor 3 Jahren

Wenn ich Dich richtig verstehe, dann sprichst Du einfach von einem Rucksackproblem
Hatten wir in verschiedenen Variationen schon hunderte Male im Forum 😉
Daher ist es immer wichtig das eigentliche Problem zu beschreiben, wie man hier wieder sieht.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Ja, allerdings so ganz konnte ich das noch nicht durchdringen, wie ich das basteln soll, wenn ich ehrlich bin.

Hier sind es 3 Rucksäcke, wobei jedes Element (jeder Gegenstand) immer alle 3 Rucksäcke beeinflusst. Dazu hat jedes Element eine Gewichtung für jeden Rucksack, die dann mit der errechneten Menge multipliziert werden muss.

Gewichtung Element 1 = { 0.21, 0.84, 0 }
Gewichtung Element 2 = { 0.133, 0.56, 0.31 }
..
Gewichtung Element n = { 0.011, 0.024, 0.5 }

Mögliche Mengen Element 1: 0 .. 30
Mögliche Mengen Element 2: 1 .. 30
Mögliche Mengen Element 3: 100 ... 500
...
Mögliche Mengen Element n: 50 .. 150

Kapazität Rucksack 1: 40
Kapazität Rucksack 2: 20
Kapazität Rucksack 3: 45

Gefunden werden muss für jedes Element die optimale Menge zwischen den Grenzen, um jeden Rucksack möglichst voll zu packen. Jedes Element hat eine untere und obere Schranke zwischen der sich die Menge bewegen dürfen.

On Top: zweige 5 besten 5 Lösungen an.

Vielleicht hab ich das aktuell blöd umgesetzt, aber zumindest komme ich so zu meinem Ergebnis. Von der Laufzeit her ist es nicht so toll, wenn mehr Elemente hinzu kommen.

Bin dazu hergegangen und hab für jedes Element 1 .. n eine eigene Matrix erstellt, in der in jeder Zeile ein Wert für jeden Rucksack drin steht, der die Menge * Gewicht enthält. Jede Zeile also von der Untergrenze bis zur Obergrenze. Für Element 1 sind das zum Beispiel 31 Zeilen für die möglichen Mengen 0 .. 30. Also jede Zeile hat 3 Spalten mit Menge * Gewicht für jeden Rucksack.

Danach bilde ich alle Kombinationsmöglichkeiten in einer Rekursion. In dem Zuge Bilde ich gleich die Spalten-Summen, die ja den Füllgrad des jeweiligen Rucksacks bilden. Ich checke da auch, ob noch eine höhere Menge in den Rucksack passt.

Um zu prüfen, welche der möglichen Lösungen die beste ist, hab ich einen Fehlerwert errechnet, der den Abstand/Fehler zum Limit der Rucksäcke ergibt:

Fehler = (Kapazität Rucksack 1 - Summe Spalte 1) + (Kapazität Rucksack 2 - Summe Spalte 2) + (Kapazität Rucksack 3 - Summe Spalte 3)

Wenn man alle Kombinationen der Matrizen gebildet hat, kann man nach dem Minimum der Fehlerwerte suchen. Der kleineste Fehlerwert ist dann die optimalste Füllmenge, um alle Rucksäcke möglichst voll zu machen.

So viel zur Theorie. Nur, in der Praxis ist das Ausrechnen aller Kombinationen natürlich teuer und nicht so der Hit was die Performance angeht.

Hatte schon überlegt, ob ich für jede Matrix-Kombination per binärer Suche anfangen soll, die Elemente davor und danach prüfen und ob der Fehlerwert dabei kleiner oder größer wird, um dann die Suche auf den optimalere Teilbereich weiter einzugrenzen. Da hab ich mich aber glaub etwas verrannt, denn es kann durchaussein, dass man bei einem Elment eine geringere Menge nehmen sollte, dafür bei einem anderen eine höhere, damit das Ergebnis optimaler wird.

Ob sich mit dieser binären Variante so überhaupt das Problem errechnen lässts, weiß ich noch nicht.

Eine Implementierung für 3 Rucksäcke und den Randbedingungen, wie oben beschrieben, ist mir bisher noch nicht gelungen, außer der über Berechnung aller Kombinationen, was aber von der Laufzeit her, nicht so toll ist.

5.299 Beiträge seit 2008
vor 3 Jahren

Zum Thema Rucksack: Von Wikipedias Erklärung verstehe ich nur iwas mit Backtracking.
Läuft "dynamische Programmierung" etwa auf folgendes hinaus?

Rekursiv alle Kombinationen durchgehen und dabei die (bisher) beste merken.
Bei der rekursiven Vertiefung immer abbrechen, wenn der aktuelle Wert bereits schlechter ist als der bislang gefundene beste Wert ?

das käme mir ziemlich trivial vor, dass man nicht weiter rumprobiert, wenn man eh schon aussm Limit ist.
Ist das, was der berühmte Bellmann meinte?

Ich versteh auch nicht den Wiki-Pseudo-Code mit den verschachtelten For-Schleifen. Sollte ich das richtig verstanden haben, sehe ich da eigentlich keine andere Lösung als eine Rekursive (oder evtl. noch eine, die Rekursion iterativ emuliert, etwa mit einem Stack)

Edit: Ups - Sorry - da kam nun ein Post dazwischen

Der frühe Apfel fängt den Wurm.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Wenn ich für jedes Element schon mal die gewichteten Mengen zwischen der Untergrenze und der Obergrenze berechnet, geht das schnell. Damit hab ich Matrizen für jedes Element. Die sehen dann in etwa so aus:

Element 1
Mögliche Mengen: 1..30
Gewichte für jeden Rucksack: { 0.21, 0.84, 0 }
Matrix gewichteter Mengen:


{ 1  0.21  0.84  0,
  2  0.42  1.68  0,
  ...
  30 6.30  25.20 0
}

So eine Matrix für jedes Element 1..n wird als Input genommen.

Danach dann Berechnung aller Kombinationen/Permutationen aller Zeilen aller Matrizen!
So komme ich dann auch an die Spaltensummen für jede Kombination der Elemente 1..n und kann den Fehlerwert berechnen.

Wenn die Spaltensumme mal aus dem Ruder läuft, brauche ich in dieser Matrix nicht noch 1 Element weiter gehen, da ja dann der Fehler noch größer wird.

Also das ist aktuell so fast noch die einzige Optimierung, die mir einfällt. Ansonsten wüsste ich gerade nicht.

Ein Gedanke war wie gesagt, ob man nicht Partitionieren könnte und die Matrizen per Binärer Suche in die Hälfte teilen, schauen, ob das Ergebnis bei einer Zeile davor oder danach besser wird und dann weiter in diese Richtung suchen.

Ich befürchte nur, so richtig kann ich das damit gar nicht bewältigen, denn es könnte ja durchaus sein, dass ich bei einer der ersten Matrizen feststelle, ich sollte besser nach oben gehen, dann wird aber das Ergebnis aufgrund der errechneten gewichteten Werte für den anderen Topf irgendwo schlechter und ich müsste besser da nach unten gehen, damit es mit den anderen Matrizen und Rucksäcken noch besser wird.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Rekursiv alle Kombinationen durchgehen und dabei die (bisher) beste merken.
Bei der rekursiven Vertiefung immer abbrechen, wenn der aktuelle Wert bereits schlechter ist als der bislang gefundene beste Wert ?

Das Ding ist, man kann nur bei der Verknüpfung an der letzten Matrix den Fehlerwert genau bestimmen. Klar, wenn auf dem Weg da hin schon irgendwie der erlaubte Rucksack überlaufen ist, dann kann man abbrechen, aber so viel bringt das irgendwie nicht.

Beim Rucksackproblem mit mehreren Rucksäcken verteilt man die n Elemente optimal auf die verschiedenen Rucksäcke.

Bei mir ist es so, dass jedes Element rein muss und dabei einen gewissen Einfluß auf alle 3 Rucksäcke hat. Die genaue Menge jedes Elementes ist halt noch nicht bekannt.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Rekursiv alle Kombinationen durchgehen und dabei die (bisher) beste merken.
Bei der rekursiven Vertiefung immer abbrechen, wenn der aktuelle Wert bereits schlechter ist als der bislang gefundene beste Wert ?

Also bei meinen Input-Daten mit 6 Elementen läuft die Berechnung mittels Rekursion in etwa 40 - 45s durch.

 
            double[] weightsElement1 = new double[3] { 0.21, 0.53, 0.14 };
            double[] weightsElement2 = new double[3] { 0.841, 0.011, 0.011 };
            double[] weightsElement3 = new double[3] { 0, 0, 0.93 };
            double[] weightsElement4 = new double[3] { 0.14, 0.067, 0.56 };
            double[] weightsElement5 = new double[3] { 0.122, 0.003, 0.04 };
            double[] weightsElement6 = new double[3] { 0.003, 0.006, 0.114 };
            //double[] weightsElement7 = new double[3] { 0.004, 0.003, 0.104 };

            int[] boundariesElement1 = new int[2] { 0, 30 };
            int[] boundariesElement2 = new int[2] { 1, 30 };
            int[] boundariesElement3 = new int[2] { 5, 5 };
            int[] boundariesElement4 = new int[2] { 20, 150 };
            int[] boundariesElement5 = new int[2] { 100, 500 };
            int[] boundariesElement6 = new int[2] { 50, 100 };
            //int[] boundariesElement7 = new int[2] { 50, 150 };

           ...

Ich möchte evtl. später daraus noch ne kleine App mittels Xamarin machen, so dass man das irgendwie auch auf nem iPhone zum Laufen bekommt. Da ich plane, vielleicht bis zu 8 Elemente zur Konfiguration zu erlauben, sollte ich schon nochmal was in Sachen Performance verbessern.
Excel bekommt das bei größeren Mengen mit seinem Solver effizienter hin.

Wenn ich wüsste, wie ich das Speichern in meiner LimitedSortedList parallel richtig verwalten kann, könnte ich eine Variante mit Parallel.For(...) oder ähnlichem noch probieren. Bei mir wird das ja aktuell auf einem Core nur gemacht, denke ich mal und der Flaschenhals ist tatsächlich dann das Einfügen in die LimitedSortedList. Lasse ich die Sortierung und Begrenzung weg, dann bekomme ich schnell eben den Speicher voll und es raucht auch ab. Für ein Handy ist das ganze damit eh so gestorben.

Ich weiß nicht, wasn man am Handy an Wartezeit für so eine Berechnung akzeptieren kann, aber das muss doch auch irgendwie noch besser gehen. Der Excel-Solver bekommt das doch auch besser hin.

5.299 Beiträge seit 2008
vor 3 Jahren

Tja, ich würds gerne probieren, deinen Code zu verbessern - etwa durch Backtracking.
Allein ich sehe ihn nicht...?

Der frühe Apfel fängt den Wurm.

4.931 Beiträge seit 2008
vor 3 Jahren

Excel bekommt das bei größeren Mengen mit seinem Solver effizienter hin.

Es gibt beim Excel-Solver zwei verschiedene Möglichkeiten, je nachdem ob die CheckBox "Assume Linear Model" in den Optionen aktiviert ist oder nicht (Standard: deaktiviert):

s.a. Excel Solver - Algorithms and Methods Used sowie speziell Standard Excel Solver - Limitations of Nonlinear Optimization

Da wirst du mit deinem bisherigen Ansatz nicht herankommen.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Tja, ich würds gerne probieren, deinen Code zu verbessern - etwa durch Backtracking.
Allein ich sehe ihn nicht...?

Hier mal der bisherige Code (natürlich noch nicht optimal aufbereitet). Ist erst mal über einen Button einer Form zum Anstarten und am Ende wird noch kurz die sortierte Liste ausgegeben:


using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Windows.Forms;

namespace SolverAlgorithm
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {

        }

        /// <summary>
        /// Creates a value matrix in ascending order with the calculated value for each Quantity
        /// from its minimum to its maximum quantity
        /// </summary>
        /// <param name="weights">Proportions on each Rucksack</param>
        /// <param name="minimum">Minimum Quantity for this Element</param>
        /// <param name="maximum">Maximum Quantity for this Element</param>
        /// <returns>An array containing the calculated values (weight * quantity) and the quantity itself (e.g. [{0.22, 0.01, 0.34, 1}, {0.44, 0.02, 0.68, 2}, ..])</returns>
        private double[,] CalculateValueMatrixAscending(double[] weights, int minimum, int maximum)
        {
            int numberOfValues = Math.Abs(maximum - minimum);
            double[,] valueMatrix = new double[numberOfValues + 1, 4]; // Rucksack 1, Rucksack 2, Rucksack 3, Quantity

            for (int quantity = minimum, index = 0; quantity <= maximum; quantity++, index++)
            {
                for (int j = 0; j < 3; j++)
                {
                    valueMatrix[index, j] = quantity * weights[j];
                }

                valueMatrix[index, 3] = quantity;       // Quantity for which the value was calculated
            }

            return valueMatrix;
        }

        /// <summary>
        /// Creates a value matrix in descending order with the calculated value for each Quantity
        /// from its minimum to its maximum quantity
        /// </summary>
        /// <param name="weights">Proportions on each Rucksack</param>
        /// <param name="minimum">Minimum Quantity for this Element</param>
        /// <param name="maximum">Maximum Quantity for this Element</param>
        /// <returns>An array containing the calculated values (weight * quantity) and the quantity itself (e.g. [{0.22, 0.01, 0.34, 1}, {0.44, 0.02, 0.68, 2}, ..])</returns>
        private double[,] CalculateValueMatrixDescending(double[] weights, int minimum, int maximum)
        {
            int numberOfValues = Math.Abs(maximum - minimum);
            double[,] valueMatrix = new double[numberOfValues + 1, 4]; // Rucksack 1, Rucksack 2, Rucksack 3, Quantity

            for (int quantity = maximum, index = 0; quantity >= minimum; quantity--, index++)
            {
                for (int j = 0; j < 3; j++)
                {
                    valueMatrix[index, j] = quantity * weights[j];
                }

                valueMatrix[index, 3] = quantity;       // Quantity for which the value was calculated
            }

            return valueMatrix;
        }

        private void CalculateOptimalQuantities(int recursionDepth, double[][,] elements, double sumElement1_CurrentRecursionDepth, double sumElement2_CurrentRecursionDepth, double sumElement3_CurrentRecursionDepth, RucksackRestrictions rucksackRestrictions, LimitedSortedList sortedListOptimaleQuantities, OptimalQuantities optimalQuantitiesOverRecursion)
        {
            // Stop recursion at the lowest level (last Matrix)
            if (recursionDepth > elements.GetUpperBound(0))
                return;

            double[,] elementCurrentRecursionDepth = elements[recursionDepth];
            int numRows = elementCurrentRecursionDepth.GetUpperBound(0);  // extra variable to have the opportunity to manipulate it

            for (int row = 0; row <= numRows; row++)
            {
                // Save the quantity over the entire recursion hierarchy to
                // have the "Optimal Quantities" to the corresponding error value later on
                optimalQuantitiesOverRecursion.OptimalElementQuantities[recursionDepth] = (int)elementCurrentRecursionDepth[row, 3];      // Quantity of current line in the Matrix

                // Create sum for Columns (each column is a Rucksack) for each Element Quantity
                // of the current Matrix Combination
                var sumRucksack1 = sumElement1_CurrentRecursionDepth + elementCurrentRecursionDepth[row, 0];        // Rucksack 1
                var sumRucksack2 = sumElement2_CurrentRecursionDepth + elementCurrentRecursionDepth[row, 1];        // Rucksack 2
                var sumRucksack3 = sumElement3_CurrentRecursionDepth + elementCurrentRecursionDepth[row, 2];        // Rucksack 3

                // Determine if allowed maximum capacity of a Rucksack is exceeded and end recursion
                // Don't proceed next row/quantity as it would be even higher (when ascending order is used)
                if (sumRucksack1 > rucksackRestrictions.CapacityRucksack1 || sumRucksack2 > rucksackRestrictions.CapacityRucksack2 || sumRucksack3 > rucksackRestrictions.CapacityRucksack3)
                    return;

                CalculateOptimalQuantities(recursionDepth + 1, elements, sumRucksack1, sumRucksack2, sumRucksack3, rucksackRestrictions, sortedListOptimaleQuantities, optimalQuantitiesOverRecursion);

                // We are at the bottom of the recursion and on our last element,
                // so we can create an ErrorValue as a Distance to the allowed Maximum capacity
                // over all Rucksacks
                if (recursionDepth == elements.GetUpperBound(0))
                {
                    // The lower the better and the better the rucksacks are filled
                    var errorValue = (rucksackRestrictions.CapacityRucksack1 - sumRucksack1) + (rucksackRestrictions.CapacityRucksack2 - sumRucksack2) + (rucksackRestrictions.CapacityRucksack3 - sumRucksack3);

                    // This would be an Over-Optimization of the ErrorValue and
                    // basically should occur. So we end the recursion in this case
                    if (errorValue < 0)
                        return;

                    //// For a descending case
                    //// We iterate from the highest Quantity to the lowest Quantity and
                    //// save a value for the first time. After that save the following
                    //// x values to just show these values to the user
                    //int newEndIndex = row + sortedListOptimalQuantities.Capacity;
                    //numRows = newEndIndex <= row ? newEndIndex : row;

                    // Here we save the optimal Quantities we've collected
                    // over the levels of the recursion and with the calculated
                    // error value on the bottom of the recursion.
                    // Do a shallow copy to have a unique reference of the OptimalQuantity
                    // to save.                    
                    OptimalQuantities optimaleMengeToSave = new OptimalQuantities(optimalQuantitiesOverRecursion.OptimalElementQuantities.Length);
                    for (int i = 0; i < optimalQuantitiesOverRecursion.OptimalElementQuantities.Length; i++)
                    {
                        optimaleMengeToSave.OptimalElementQuantities[i] = optimalQuantitiesOverRecursion.OptimalElementQuantities[i];
                    }
                    optimaleMengeToSave.ErrorValue = errorValue;
                    optimaleMengeToSave.SumRucksack1 = sumRucksack1;
                    optimaleMengeToSave.SumRucksack2 = sumRucksack2;
                    optimaleMengeToSave.SumRucksack3 = sumRucksack3;

                    sortedListOptimaleQuantities.Add(optimaleMengeToSave);
                }
            }
        }

        private void cmdStartCalculation_Click(object sender, EventArgs e)
        {
#if DEBUG
            Stopwatch timer = new Stopwatch();
            timer.Start();
#endif            
            double[] weights_Element1 = new double[3] { 0.21, 0.53, 0.14 };
            double[] weights_Element2 = new double[3] { 0.841, 0.011, 0.011 };
            double[] weights_Element3 = new double[3] { 0, 0, 0.93 };
            double[] weights_Element4 = new double[3] { 0.14, 0.067, 0.56 };
            double[] weights_Element5 = new double[3] { 0.122, 0.003, 0.04 };
            double[] weights_Element6 = new double[3] { 0.003, 0.006, 0.114 };
            double[] weights_Element7 = new double[3] { 0.004, 0.003, 0.104 };

            int[] boundaries_Element1 = new int[2] { 0, 30 };       // Original boundaries: 0 - 30
            int[] boundaries_Element2 = new int[2] { 1, 30 };       // Original boundaries: 1 - 30
            int[] boundaries_Element3 = new int[2] { 5, 5 };        // Original boundaries: 5 - 5
            int[] boundaries_Element4 = new int[2] { 20, 150 };     // Original boundaries: 20 - 150
            int[] boundaries_Element5 = new int[2] { 100, 500 };    // Original boundaries: 100 - 500
            int[] boundaries_Element6 = new int[2] { 50, 100 };     // Original boundaries: 50 - 100
            int[] boundaries_Element7 = new int[2] { 50, 150 };     // Original boundaries: 50 - 150

            var valueMatrix_Element1 = CalculateValueMatrixAscending(weights_Element1, boundaries_Element1[0], boundaries_Element1[1]);
            var valueMatrix_Element2 = CalculateValueMatrixAscending(weights_Element2, boundaries_Element2[0], boundaries_Element2[1]);
            var valueMatrix_Element3 = CalculateValueMatrixAscending(weights_Element3, boundaries_Element3[0], boundaries_Element3[1]);
            var valueMatrix_Element4 = CalculateValueMatrixAscending(weights_Element4, boundaries_Element4[0], boundaries_Element4[1]);
            var valueMatrix_Element5 = CalculateValueMatrixAscending(weights_Element5, boundaries_Element5[0], boundaries_Element5[1]);
            var valueMatrix_Element6 = CalculateValueMatrixAscending(weights_Element6, boundaries_Element6[0], boundaries_Element6[1]);
            var valueMatrix_Element7 = CalculateValueMatrixAscending(weights_Element7, boundaries_Element7[0], boundaries_Element7[1]);

            IList<double[,]> elements = new List<double[,]>();
            elements.Add(valueMatrix_Element1);
            elements.Add(valueMatrix_Element2);
            elements.Add(valueMatrix_Element3);
            elements.Add(valueMatrix_Element4);
            elements.Add(valueMatrix_Element5);
            elements.Add(valueMatrix_Element6);
            //elements.Add(valueMatrix_Eleent7);


            // Maybe implement a check here, if there could be a calculation at all (e.g. if in ascending order the minimum is already an overflow)
            // ...


            LimitedSortedList limitedSortedListOptimalQuantities = new LimitedSortedList(5);
            RucksackRestrictions rucksackRestrictions = new RucksackRestrictions(40, 20, 45);
            var elementArray = elements.ToArray();

            // Create all Matrix-Combinations line by line and do the calculations
            var firstElement = elements[0];
            for (int i = 0; i <= firstElement.GetUpperBound(0); i++)
            {
                OptimalQuantities optimalQuantities = new OptimalQuantities(elements.Count);
                optimalQuantities.OptimalElementQuantities[0] = (int)firstElement[i, 3];

                double sumElement1_CurrentRecursionDepth = firstElement[i, 0];
                double sumElement2_CurrentRecursionDepth = firstElement[i, 1];
                double sumElement3_CurrentRecursionDepth = firstElement[i, 2];

                CalculateOptimalQuantities(1, elementArray, sumElement1_CurrentRecursionDepth, sumElement2_CurrentRecursionDepth, sumElement3_CurrentRecursionDepth, rucksackRestrictions, limitedSortedListOptimalQuantities, optimalQuantities);
            }

#if DEBUG
            timer.Stop();
            Debug.WriteLine($"Time Taken for Calculation: {timer.Elapsed.Minutes}m {timer.Elapsed.Seconds}s {timer.Elapsed.Milliseconds}ms");
#endif      

            // Just a simple output in Debug Console
            foreach (var optimalQuantity in limitedSortedListOptimalQuantities)
            {
                Debug.WriteLine($"{optimalQuantity}");
            }
        }
    }
}


using System.Collections;
using System.Collections.Generic;

namespace SolverAlgorithm
{
    class LimitedSortedList : IList<OptimalQuantities>
    {
        private IList<OptimalQuantities> limitedList = new List<OptimalQuantities>();

        public LimitedSortedList(int capacity)
        {
            this.Capacity = capacity;
        }



        public int Capacity { get; private set; }

        public OptimalQuantities this[int index] { get => limitedList[index]; set => throw new System.NotImplementedException(); }

        public int Count => limitedList.Count;

        public bool IsReadOnly => limitedList.IsReadOnly;

        public void Add(OptimalQuantities item)
        {
            int positionToInsert = limitedList.Count;
            for (int i = 0; i < limitedList.Count; i++)
            {
                if (item.CompareTo(limitedList[i]) < 0)
                {
                    positionToInsert = i;
                    break;
                }
            }

            limitedList.Insert(positionToInsert, item);

            if (limitedList.Count > this.Capacity)
                limitedList.RemoveAt(limitedList.Count - 1);
        }

        public void Clear()
        {
            limitedList.Clear();
        }

        public bool Contains(OptimalQuantities item)
        {
            return limitedList.Contains(item);
        }

        public void CopyTo(OptimalQuantities[] array, int arrayIndex)
        {
            limitedList.CopyTo(array, arrayIndex);
        }

        public IEnumerator<OptimalQuantities> GetEnumerator()
        {
            return limitedList.GetEnumerator();
        }

        public int IndexOf(OptimalQuantities item)
        {
            return limitedList.IndexOf(item);
        }

        public void Insert(int index, OptimalQuantities item)
        {
            throw new System.NotImplementedException();
        }

        public bool Remove(OptimalQuantities item)
        {
            return limitedList.Remove(item);
        }

        public void RemoveAt(int index)
        {
            limitedList.RemoveAt(index);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return limitedList.GetEnumerator();
        }
    }
}


using System;

namespace SolverAlgorithm
{
    class OptimalQuantities : IEquatable<OptimalQuantities>, IComparable<OptimalQuantities>
    {
        readonly int[] optimalElementQuantities;

        public OptimalQuantities(int numProducts)
        {
            this.optimalElementQuantities = new int[numProducts];
        }
        
        /// <summary>
        /// Optimal Quantities from first Element to last Element that has to be used
        /// </summary>
        public int[] OptimalElementQuantities { get => this.optimalElementQuantities; }
        public double ErrorValue { get; set; }

        public double SumRucksack1 { get; set; }
        public double SumRucksack2 { get; set; }
        public double SumRucksack3 { get; set; }


        public override string ToString()
        {
            return $"ErrorValue: {ErrorValue}; Sum Rucksack 1: {SumRucksack1}, Sum Rucksack 2: {SumRucksack2}, Sum Rucksack 3: {SumRucksack3}";
        }

        public int CompareTo(OptimalQuantities other)
        {
            // A null value means that this object is greater.
            if (other == null)
                return 1;
            else
                return this.ErrorValue.CompareTo(other.ErrorValue);
        }

        public override int GetHashCode()
        {
            return this.ToString().GetHashCode();
        }

        public override bool Equals(object obj)
        {
            if (obj == null) return false;
            OptimalQuantities objAsOptimaleMenge = obj as OptimalQuantities;
            if (objAsOptimaleMenge == null) return false;
            else return Equals(objAsOptimaleMenge);
        }        

        public bool Equals(OptimalQuantities other)
        {
            if (other == null)
                return false;

            return  (other.ErrorValue == this.ErrorValue) && 
                    (other.SumRucksack1 == this.SumRucksack1) && 
                    (other.SumRucksack2 == this.SumRucksack2) && 
                    (other.SumRucksack3 == this.SumRucksack3);
        }
    }
}


namespace SolverAlgorithm
{
    class RucksackRestrictions
    {
        public int CapacityRucksack1 { get; }
        public int CapacityRucksack2 { get; }
        public int CapacityRucksack3 { get; }

        public RucksackRestrictions(int capacityRucksack1, int capacityRucksack2, int capacityRucksack3)
        {
            this.CapacityRucksack1 = capacityRucksack1;
            this.CapacityRucksack2 = capacityRucksack2;
            this.CapacityRucksack3 = capacityRucksack3;
        }
    }
}

Den Versuch/Ansatz mit Partitionierung der Matrizen, ähnlich binärer Suche, hab ich mal raus gelassen.

Zumindest über die Schleife für die erste Matrix wollte ich gerne eine Parallel.For(...) probieren. Kannst aber ja vergessen mit der LimitedSortedList.

Ohne diese Spaßbremse "LimitedSortedList" läuft sehr schnell auch der Speicher voll. Da kannst dem Untergang zusehen.

Wie gesagt, ich wollte das gerne auch noch auf mein Handy bringen, so dass Performance und Speicher schon auch echte Beschränkungen sind.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Beim Überfliegen der Artikel sehe ich das ehrlich gesagt auch so.

Im Grunde wäre es mir wichtig, dass ich eine Lösung auf eine kleine Handy-App bringe. Für mich gedacht, von daher kann ich mit leicht höheren Laufzeiten leben, aber natürlich auch nicht übermäßig, ansonsten wird es auch eine zähe angelegenheit.

Ist Dir zufällig ein guter frei verwendbarer Solver bekannt, den man für solche Berechnungen hernehmen könnte?

Hinweis von Abt vor 3 Jahren

Bitte keine Full Quotes, muss dauernd Deine Beiträge editieren.
Muss echt nicht sein.

5.299 Beiträge seit 2008
vor 3 Jahren

uff - da bin ich draussen - Knapsack hoch 3!
Bin grade erst dabei Knapsack überhaupt zu kapieren - es ist nicht einfach nur Backtracking.
Tatsächlich ist der Standard-Algo zum Matrix-Füllen nichtmal rekursiv, und auch das anschliessende Auswerten derselben nicht.
Also ich weiss nicht, ob die bei Wikipedia einen richtigen Begriff von Backtracking haben, oder ich - bei mir ist Backtracking rekursiv.
Hier auf myCsharp finde ich auch nix wirkliches zum Knapsack, nur Beiträge, in denen behauptet wird, das sei erledigt, und im besten Falle noch: man solle da und da gucken...
Oft aber auch nur: Man solle selber gucken 8o (ohne da und da)

Hier fand ich schliesslich den Standard-Algo: https://www.programmingalgorithms.com/algorithm/knapsack-problem/
Allerdings ohne die Auswertung der Matrix - das fund ich hier: https://www.proggen.org/doku.php?id=algo:knapsack
Und auch eine mir verständliche Erklärung. Aber die haben eine rekursive Implementierung - vmtl. bisserl suboptimal.
/OT

Ich glaub garnet, dass man da was paralellisieren kann. Bei Knapsack hängt eine Teil-Lösung doch ab von zuvor gefundenen Teil-Lösungen - das kann man doch garnet nebeneinander her-wursteln lassen.

Der frühe Apfel fängt den Wurm.

O
OXO Themenstarter:in
86 Beiträge seit 2020
vor 3 Jahren

Ich hab es jetzt mit meiner eigenen Lösung doch aufgegeben.

Der Google OR Tools Solver kann mit einem "SCIP"-Solver in Windeseile lösen. Die Lösung kommt sogar deutlich schneller, als mit dem Excel-Solver. Evtl. hab ich bei Excel durch Setzen eines Hakens noch etwas suboptimal konfiguriert, wenn das hier so schnell geht.

Die Konfiguration ist als Neuling allerdings etwas gewöhnungsbedürftig, aber wenn man die mal raus hat und wie man Gleichungen bzw. Constraints für den Solver bastelt, dann macht er wirklich gute Arbeit.

Frage ist nur noch, ob diese OR Tools überhaupt auf meinem iPhone und mit Xamarin zum Laufen zu bringen sind... Hürden über Hürden. Ansonsten muss ich doch wieder auf meine manuell programmierte Variante gehen..