Mögliche Zusammenstellung von Waren berechnen

Guten Nachmittag,

nehmen wir mal an, ich bin ein Händler und verkaufe irgendwelche Waren.
Der Kunde gibt an, dass er von Artikel A genau 3250 Stück auf 5 Kisten verteilt haben will.

Gleichzeitig sind die Mengen in den Kisten aber stark verschieden.
So könnte man z.B. sagen, es sind folgende Kisten verfügbar:
1 x 330 Stück
1 x 390 Stück
2 x 460 Stück
1 x 660 Stück
1 x 720 Stück
1 x 780 Stück
32 x 810 Stück
14 x 900 Stück

Die Mengen hab ich nicht aufeinander angepasst, kann also sein, dass das gar nicht passt.

Ich weiß zwar, wie viel Stück in einer Kiste sein sollten, kann aber nicht davon ausgehen, dass dem auch so ist.
Ich brauche also eine Logik, die mir die Kisten zuordnen kann.
Sie soll die Kisten so auswählen, dass am Ende genau 5 Kisten mit genau 3250 Stück raus kommen.

Kennt da jemand eine "einfache" Möglichkeit?
Mir fallen spontan nur zwei ein:*Brute Force - so lange ausprobieren, bis es passt *Ein Genetischer Algorithmus

Außerdem muss ich voraus sagen können, ob die Zuordnung überhaupt möglich ist.
Bei der Brute-Force-Methode geht das, allerdings ist das je nach Umfang der Daten irre Rechenintensiv.
Bei einem genetischen Algorithmus kann ich eigentlich nie sicher sagen, ob das geht, ich kann nur sagen, dass der irgendwann abbricht.

Beste Grüße

Rucksackproblem =)

Das sieht doch auf den ersten Blick so aus, als wäre das Thema schon von genug Leuten tot gedacht und auch gelöst worden 😄

Ich werd mich mal rein lesen, danke für den Link ^^

Also das gute ist: Wir wissen jetzt, dass es keine Lösung gibt X(
Das Schlechte: Wir müssen uns einen Weg suchen, wir wir ohne ewig lange Laufzeiten doch ein Ergebnis suchen.

Unsere Idee dazu:
Wir nutzen die Brute-Force-Lösung mit Timeout.
Wir lassen also alle möglichen Kombinationen durch rechnen, bis das erste passende Ergebnis erreicht wird. Wir haben da ja noch den Vorteil, dass wir potentiell nicht alles durch rechnen müssen, da es den Fall, dass es passt, theoretisch mehrfach gibt.
Dazu messen wir noch die Dauer einer kompletten Berechnung eines "üblichen" Durchgangs und neben das dann als Timeout.

Kommt die Berechnung zu einem Ergebnis: Cool
Dauert sie zu lange: Muss ein Nutzer das nochmal manuell anstoßen und die Arbeit selber erledigen.

Hallo Palladin007,

brute-force ist immer so brutal 😉
Vllt. schaust du dir auch [Artikel] Simulated Annealing an. Damit kann parallel (einfach mehrere "Instanzen" davon laufen lassen) optimiert werden. Im Floor-Planning wird dieser Algorithmus auch erfolgreich angewandt und so ganz verschieden sind diese Probleme nicht.

Genetische Algorithmen hast du schon selbst erwähnt und diese wären, wie viele andere Algorithmen der Gruppe "evolutionär", ebenfalls anwendbar.

Letztlich geht es immer eine Kombination zu wählen und diese per "Fitnessfunktion" in ihrer Güte zu bewerten und folglich diese Fitnessfunktion zu optimieren (min / max je nach Definition der Funktion).

Rein vom Gefühl her würde ich neben dem "klassischen" Algorithmus zur Lösung vom Rucksackproblem auf Simulated Annealing setzen.
Eigentlich würde ich eher beide parallel laufen lassen und dann je nach Ergebnis entscheiden welches verwendet wird.

mfG Gü

Das kannte ich bis jetzt noch nicht, danke für den Tipp. 😃

Aber ja: Brute-Force ist brutal, aber auch die am einfachsten und damit am schnellsten umsetzbare Lösung.
Grob über den Daumen gepeilt könnte das zeitlich noch im Rahmen sein, das gilt es aber zu testen.

Bevor ich mehr Aufwand investiere und den "Simulated Annealing"-Algorithmus (den ich ja auch erst einmal kapieren muss) oder gar einen genetischen Algorithmus implementiere, probier ich erst mal aus, ob die Brute-Force-Variante schon ausreicht.

Wenn du mal etwas schnell dahingerotztes und dreckiges dazu sehen möchtest

namespace ConsoleApp45
{
    class Program
    {
        static void Main(string[] args)
        {
            Calculate(3250, 5);
        }

        static void Calculate(int amount, int parcelCount)
        {
            var sw = Stopwatch.StartNew();

            var parcelquery = GetAllParcels()
                .Select(e => new
                {
                    Amount = Math.Min(e.Amount, parcelCount),
                    Capacity = e.Capacity,
                    Order = Math.Abs(e.Capacity - amount / parcelCount)
                })
                .OrderBy(e => e.Order)
                .SelectMany(e => Enumerable.Range(1, e.Amount).Select(x => new { Capacity = e.Capacity, Order = e.Order }));

            var resultlist = parcelquery.Combinate(parcelCount)
                .Where(e => e.Sum(p => p.Capacity) >= amount)
                .Select(e => e.OrderBy(p => p.Capacity).ToList())
                .OrderBy(e => e.Sum(p => p.Capacity))
                .Select(e => $"{string.Join(",", e.Select(p => p.Capacity.ToString()))} - {e.Sum(p => p.Capacity)}")
                .Distinct()
                .ToList();

            sw.Stop();

            foreach (var result in resultlist)
            {
                Console.WriteLine(result);
            }
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
        }

        static IEnumerable<Parcel> GetAllParcels()
        {
            yield return new Parcel { Amount = 1, Capacity = 330, };
            yield return new Parcel { Amount = 1, Capacity = 390, };
            yield return new Parcel { Amount = 2, Capacity = 460, };
            yield return new Parcel { Amount = 1, Capacity = 660, };
            yield return new Parcel { Amount = 1, Capacity = 720, };
            yield return new Parcel { Amount = 1, Capacity = 780, };
            yield return new Parcel { Amount = 32, Capacity = 810, };
            yield return new Parcel { Amount = 14, Capacity = 900, };
        }

    }

    static class EnumerableExtensions
    {
        public static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource item)
        {
            if (source == null)
                throw new ArgumentNullException(nameof(source));

            yield return item;

            foreach (var element in source)
                yield return element;
        }

        public static IEnumerable<IEnumerable<TSource>> Permutate<TSource>(this IEnumerable<TSource> source)
        {
            if (source == null)
                throw new ArgumentNullException(nameof(source));

            var list = source.ToList();

            if (list.Count > 1)
                return from s in list
                       from p in Permutate(list.Take(list.IndexOf(s)).Concat(list.Skip(list.IndexOf(s) + 1)))
                       select p.Prepend(s);

            return new[] { list };
        }

        public static IEnumerable<IEnumerable<TSource>> Combinate<TSource>(this IEnumerable<TSource> source, int k)
        {
            if (source == null)
                throw new ArgumentNullException(nameof(source));

            var list = source.ToList();
            if (k > list.Count || k < 0)
                throw new ArgumentOutOfRangeException(nameof(k));

            if (k == 0)
                yield return Enumerable.Empty<TSource>();
            else
                for (int i = 0; i < list.Count - k; i++)
                {
                    foreach (var c in Combinate(list.Skip(i + 1), k - 1))
                        yield return c.Prepend(list[i]);
                }
        }

    }


    class Parcel
    {
        public int Capacity { get; set; }
        public int Amount { get; set; }
    }

}

Das sieht nach der Brute-Force-Variante aus?

Aber ich bin erstaunt, wie schnell das geht.
Das lässt hoffen, dass ich das auch auf mehrere Aufträge erweitern kann und in einem annehmbaren zeitlichen Rahmen bleibe.
Langwierig wird nur, die Daten auch in den RAM zu bekommen. Gerade bei mehreren Aufträgen und einigen 1000 Datensätzen müssen die Daten so aufbereitet werden, dass am Ende möglichst wenig für die eigentliche Berechnung übrig bleiben.
Aber das sollte sich mit einer klugen Query lösen lassen.

Aber ich probier mal, das auf Basis der Produktiv-Daten ans Laufen zu bekommen um zu schauen, wie lange das dauert. Vielleicht sind meine Sorgen wegen der Laufzeit ja auch gänzlich unbegründet.