Der beste Weg, um die Liste der Doubles zu gruppieren, um einen bestimmten Wert zu addieren

Question

Ich habe die Aufgabe, dass ich unsicher bin, wie ich angehen sollte.

Es gibt eine Liste von Doppelpunkten, und ich muss sie zusammen gruppieren, um einen bestimmten Wert hinzuzufügen.

sagen, ich habe: 14,6666666666666, 14,6666666666666, 2,37499999999999, 1,04166666666665, 1,20833333333334, 1,20833333333334, 13,9583333333333, 1,20833333333334, 3,41666666666714, 3,41666666666714, 1,20833333333334, 1,20833333333334, 14,5416666666666, 1,20833333333335, 1.04166666666666,

Und ich würde gerne in Set-Werte gruppieren wie 12,14,16

Ich möchte den höchsten Wert in der Liste nehmen dann gruppieren Sie es mit kurzen, um den nächsten Wert oben zu gleich.

Beispiel: nehmen Doppel 14.66666666666666, und gruppieren Sie es mit 1.20833333333334, um mich nahe 16 zu bringen, und wenn es noch kleine Doppel in der Liste übrig bleiben, gruppieren Sie sie auch.

Dann bewegen Sie in der Liste auf das nächste Doppel auf ..

Answer 1

Das ist buchstäblich das "Schneiden Lager Problem" (manchmal als das 1 Dimensional Bin Packing Problem). Es gibt eine Reihe gut dokumentierter Lösungen.

• Der einzige Weg, um die „Optimal“ Lösung (außer einem Quantencomputer) zu erhalten, ist durch jede Kombination zu Zyklus, und wählen Sie das beste Ergebnis.

• Ein schneller Weg, um eine "OK" -Lösung zu erhalten, wird der "First Fit Algorithmus" genannt. Es nimmt die angeforderten Werte in der Reihenfolge, in der sie kommen, und entfernt sie aus dem ersten Material, das die Anforderung erfüllen kann.

• Der "First Fit Algorithm" kann leicht verbessert werden, indem die Werte vom größten zum kleinsten vorbestellt und die Materialien vom kleinsten zum größten vorbestellt werden.Sie können auch das Material verwenden, das der Anforderung am nächsten kommt, anstatt das erste, das die Anforderung erfüllen kann.

• Ein Kompromiss, aber einer, der mehr Code erfordert, ist ein "Genetischer Algorithmus". Dies ist eine übermäßige Vereinfachung, aber Sie könnten die Grundidee des "First Fit Algorithm" verwenden, aber zufällig zwei der Werte vor jedem Durchlauf austauschen. Wenn die Effizienz steigt, behalten Sie die Änderung bei, und wenn sie abnimmt, kehren Sie zum letzten Zustand zurück. Wiederholen Sie dies, bis eine bestimmte Zeit verstrichen ist oder bis Sie zufrieden sind.

Answer 2

das Doppel in einer Liste setzen und sie sortieren. Ergreifen Sie den höchsten Wert, der kleiner als das zu startende Ziel ist. Durchlaufen Sie dann vom Anfang der Liste bis zum Erreichen eines Punktes, an dem Sie den Grenzwert überschreiten.

var threshold = 16; 
List<double> values = new List<double>(); 
values.Add(14.932034); 
etc... 

Sortieren Sie die Liste:

values = values.OrderBy(p => p).ToList(); 

Zupacken der höchste Wert, der kleiner als der Schwellenwert ist:

// Highest value under threshold 
var highestValue = values.Where(x => x < threshold).Max(); 

Jetzt Ihre Suche und Berechnungen durchführen, bis Sie Ihre Lösung erreichen:

currentValue = highestValue 
Console.WriteLine("Starting with: " + currentValue); 
foreach(var val in values) 
{ 
    if(currentValue + val <= theshold) 
    { 
     currentValue = currentValue + val; 
     Console.WriteLine(" + " + val.ToString()); 
    } 
    else 
     break; 
} 

Console.WriteLine("Finished with: " + currentValue.ToString()); 
Console.ReadLine(); 

Wiederholen Sie den Vorgang für den nächsten Wert usw., bis Sie alle gewünschten Lösungen ausgegeben haben.