Das Bruchteil-Rucksack-Problem in C++ bezieht sich darauf, eine Möglichkeit zu finden, eine Tasche mit Gegenständen eines bestimmten Gewichts und Gewinns so zu füllen, dass die Tasche den maximalen Wert enthält, ohne die Höchstgrenze zu überschreiten.
So lösen Sie das Fractional Knapsack-Problem in C++
Bestimmen Sie anhand einer Reihe von Artikeln mit jeweils gegebenem Gewicht und Gewinn die Anzahl der Artikel in einer solchen Kombination, dass das Gesamtgewicht der Artikel unter der Höchstgrenze des Beutels liegt, der Wert jedoch so groß wie möglich gehalten werden muss.
Algorithmus zur Implementierung des fraktionierten Rucksackproblems
Die Funktionsweise des Knapsack-Algorithmus lässt sich anhand der folgenden Punkte verstehen:
- Nehmen Sie zwei Arrays von Gewicht und Gewinn.
- Stellen Sie den maximalen Sackwert auf W ein.
- Bestimmen Sie die Dichte, indem Sie das Verhältnis beider Parameter bilden.
- Sortieren Sie die Elemente in absteigender Reihenfolge der Dichte.
- Addieren Sie die Werte, bis es <=W ist.
Der gierige Ansatz zur Lösung des fraktionierten Rucksackproblems
Der Greedy-Ansatz zielt darauf ab, bei jedem Schritt ideale Entscheidungen zu treffen, die am Ende zur idealen Lösung führen. Es löst Probleme Schritt für Schritt und führt zu Schlussfolgerungen, anstatt erst am Ende zu Ergebnissen zu gelangen. Dies ist ein Quellcode zur Implementierung einer Lösung für das Bruchteil-Rucksack-Problem in C++:
#include
verwenden Namensraum std ;
Struktur Objekt {
int Wert, Gewicht ;
Objekt ( int Wert, int Gewicht )
: Wert ( Wert ) , Gewicht ( Gewicht )
{
}
} ;
bool cmp ( Struktur Objekt x, Struktur Objekt y )
{
doppelt A1 = ( doppelt ) X. Wert / X. Gewicht ;
doppelt A2 = ( doppelt ) Und. Wert / Und. Gewicht ;
zurückkehren A1 > A2 ;
}
doppelt fraktionalKnapsack ( Struktur Objekt-Arr [ ] ,
int IN, int Größe )
{
Sortieren ( arr, arr + Größe, cmp ) ;
int curWeight = 0 ;
doppelt Endwert = 0,0 ;
für ( int ich = 0 ; ich < Größe ; ich ++ ) {
Wenn ( curWeight + arr [ ich ] . Gewicht <= IN ) {
curWeight + = arr [ ich ] . Gewicht ;
Endwert + = arr [ ich ] . Wert ;
}
anders {
int bleiben = IN - curWeight ;
Endwert + = arr [ ich ] . Wert
* ( ( doppelt ) bleiben
/ arr [ ich ] . Gewicht ) ;
brechen ;
}
}
zurückkehren Endwert ;
}
int In = 60 ;
Objekt-Arr [ ] = { { 100 , zwanzig } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int Größe = Größe von ( arr ) / Größe von ( arr [ 0 ] ) ;
cout << „Maximaler Gewinn =“
<< fraktionalKnapsack ( arr, v, Größe ) ;
zurückkehren 0 ;
}
In diesem Code wird eine Objektstruktur definiert, in der Gewichts- und Gewinnwerte gespeichert sind. Der boolesche Wert cmp() wird verwendet, um einen Vergleich zwischen zwei Objekten auf der Grundlage des Verhältnisses von Gewicht und Wert zweier Objekte durchzuführen. Das Array wird in absteigender Reihenfolge angeordnet und der Wert wird so lange addiert, bis er das Maximum erreicht. Wenn der aktuelle Wert zulässig ist und innerhalb der Grenze liegt, wird er addiert, andernfalls wird sein reduziertes Verhältnis zum Beutel hinzugefügt. Die Größe von Gewicht und Wert wird in den Hauptcode eingegeben und der maximale Gewinn wird auf der Ausgabe gedruckt.
Der maximale Gewinn, der im Snack gespeichert wurde, beträgt 580.
Abschluss
Das Bruchteil-Rucksack-Problem in C++ bezieht sich darauf, eine Möglichkeit zu finden, eine Tasche mit Gegenständen eines bestimmten Gewichts und Gewinns so zu füllen, dass die Tasche den maximalen Wert enthält, ohne die Höchstgrenze zu überschreiten. Dies kann durch den Greedy-Ansatz erreicht werden, der darauf abzielt, bei jedem Schritt ideale Entscheidungen zu treffen, die am Ende zur idealen Lösung führen.