Ułamkowy problem plecakowy: algorytm zachłanny z przykładem
Sara Chen
Czym jest zachłanna strategia?
Algorytmy zachłanne są podobne do algorytmów programowania dynamicznego i często stosuje się je do rozwiązywania optymalnych problemów (znajdowania najlepszych rozwiązań problemu według określonego kryterium).
Chciwe algorytmy implementują optymalne lokalne selekcje w nadziei, że te selekcje doprowadzą do optymalnego globalnego rozwiązania problemu, który ma zostać rozwiązany. Chciwe algorytmy często nie są zbyt trudne do skonfigurowania, szybkie (złożoność czasowa jest często funkcją liniową lub bardzo często funkcją drugiego rzędu). Poza tym, te programy nie są trudne do debugowania i wykorzystują mniej pamięci. Ale wyniki nie zawsze są optymalnym rozwiązaniem.
Strategie zachłanne są często używane do rozwiązania problemu optymalizacji kombinatorycznej poprzez zbudowanie opcji A. Opcja A jest konstruowana poprzez wybieranie każdego składnika Ai z A aż do ukończenia (wystarczająca liczba n komponentów). Dla każdego Ai wybierasz Ai optymalnie. W ten sposób możliwe jest, że w ostatnim kroku nie będziesz miał nic do wyboru, jak tylko zaakceptować ostatnią pozostałą wartość.
Istnieją dwa kluczowe elementy zachłannych decyzji:
- Sposób wyboru zachłannego. Możesz wybrać, które rozwiązanie jest najlepsze w danym momencie, a następnie rozwiązać podproblem wynikający z dokonania ostatniego wyboru. Wybór algorytmów zachłannych może zależeć od poprzednich wyborów. Nie może jednak zależeć od żadnego przyszłego wyboru ani od rozwiązań podproblemów. Algorytm ewoluuje w sposób, który dokonuje wyborów w pętli, jednocześnie zmniejszając dany problem do mniejszych podproblemów.
- Optymalna podbudowa. Optymalną podstrukturę problemu wykonujesz, jeśli optymalne rozwiązanie tego problemu zawiera optymalne rozwiązania jego podproblemów.
Algorytm zachłanny składa się z pięciu elementów:
- Zbiór kandydatów, z których można tworzyć rozwiązania.
- Funkcja selekcji służąca do wybrania najlepszego kandydata do dodania do rozwiązania.
- Funkcja wykonalności służy do decydowania, czy kandydat może zostać wykorzystany do zbudowania rozwiązania.
- Funkcja celu, ustalająca wartość rozwiązania lub rozwiązania niekompletnego.
- Funkcja oceny, wskazująca, kiedy znajdziesz kompletne rozwiązanie.
Idea chciwego
W przypadku pierwszego pomysłu mamy następujące kroki Greedy One:
- Sortuj w nierosnącej kolejności wartości.
- Z kolei rozpatrz zamówione paczki, rozpatrującą paczkę włóż do plecaka, jeśli pozostała pojemność plecaka jest wystarczająca, aby ją pomieścić (co oznacza, że łączna waga paczek, które zostały włożone do plecaka oraz waga paczek rozpatrywanych nie przekraczają pojemność plecaka).
Jednak ten zachłanny algorytm nie zawsze daje optymalne rozwiązanie. Tutaj masz kontrprzykład:
- Parametry problemu to: n = 3; M = 19.
- Pakiety: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Świetna wartość, ale także świetna waga.
- Algorytm wybierze pakiet 1 o łącznej wartości 20, natomiast wybrane zostanie optymalne rozwiązanie problemu (pakiet 2, pakiet 3) o łącznej wartości 24.
Pomysł Chciwej Dwójki
W przypadku drugiego pomysłu masz następujące kroki Greedy Two:
- Sortuj w niemalejącej kolejności wag.
- Z kolei rozpatrz zamówione paczki, rozpatrującą paczkę włóż do plecaka, jeśli pozostała pojemność plecaka jest wystarczająca, aby ją pomieścić (co oznacza, że łączna waga paczek, które zostały włożone do plecaka oraz waga paczek rozpatrywanych nie przekraczają pojemność plecaka).
Jednak ten zachłanny algorytm nie zawsze daje optymalne rozwiązanie. Tutaj masz kontrprzykład:
- Parametry problemu to: n = 3; M = 11.
- Pakiety: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Lekka, ale wartość jest również bardzo lekka.
- Algorytm wybierze (pakiet 1, pakiet 2) o łącznej wartości 26, natomiast optymalnym rozwiązaniem problemu będzie (pakiet 3) o łącznej wartości 28.
Idea Chciwej Trójki
W przypadku trzeciego pomysłu masz następujące kroki Greedy Three. W rzeczywistości jest to najszerzej stosowany algorytm.
- Sortuj paczki w kolejności niezwiększającej wartości kosztu jednostkowego
. Ty masz:
- Z kolei rozpatrz zamówione paczki, rozpatrującą paczkę włóż do plecaka, jeśli pozostała pojemność plecaka jest wystarczająca, aby ją pomieścić (co oznacza, że łączna waga paczek, które zostały włożone do plecaka oraz waga paczek rozpatrywanych nie przekraczają pojemność plecaka).
Pomysł: Chciwy pomysł tego problemu polega na obliczeniu 
stosunek każdego 
. Następnie posortuj te współczynniki w kolejności malejącej. Wybierzesz najwyższy paczka i pojemność plecaka, która może pomieścić tę paczkę (pozostają > wi). Każde włożenie paczki do plecaka powoduje również zmniejszenie pojemności plecaka.
Sposób wyboru pakietów:
- Rozważ szereg kosztów jednostkowych. Pakiety wybierasz według malejących kosztów jednostkowych.
- Załóżmy, że znalazłeś częściowe rozwiązanie: (x1,…, Xi).
- Wartość plecaka uzyskuje się:
- Odpowiadające wadze paczek, które zostały włożone do plecaka:
- Zatem pozostały limit wagowy plecaka wynosi:
Kroki algorytmu
Widzisz, jest to problem ze znalezieniem max. Lista pakietów jest posortowana w kolejności malejącej według kosztów jednostkowych, aby uwzględnić rozgałęzienie.
- Krok 1: Korzeń węzła reprezentuje początkowy stan plecaka, w którym nie wybrano żadnego pakietu.
- Wartość całkowita = 0.
- Górna granica węzła głównego UpperBound = M * Maksymalny koszt jednostkowy.
- Krok 2: Główny węzeł będzie miał węzły podrzędne odpowiadające możliwości wybrania pakietu o największym koszcie jednostkowym. Dla każdego węzła ponownie obliczasz parametry:
- TotalValue = TotalValue (stare) + liczba wybranych pakietów * wartość każdego pakietu.
- M = M (stare) – liczba wybranych opakowań * waga każdego opakowania.
- UpperBound = TotalValue + M (nowy) * Koszt jednostkowy opakowania, który należy uwzględnić w następnej kolejności.
- Krok 3: W węzłach podrzędnych priorytetem będzie rozgałęzienie dla węzła mającego większą górną granicę. Dzieci tego węzła odpowiadają możliwości wyboru kolejnego pakietu o dużym koszcie jednostkowym. Dla każdego węzła należy przeliczyć parametry TotalValue, M, UpperBound zgodnie ze wzorem podanym w kroku 2.
- Krok 4: Powtórz krok 3 z uwagą: w przypadku węzłów, których górna granica jest niższa lub równa wartości tymczasowego maksymalnego kosztu znalezionej opcji, nie trzeba już rozgałęziać się dla tego węzła.
- Krok 5: Jeśli wszystkie węzły są rozgałęzione lub odcięte, należy szukać najdroższej opcji.
Pseudokod algorytmu:
Fractional Knapsack (Array W, Array V, int M) 1. for i <- 1 to size (V) 2. calculate cost[i] <- V[i] / W[i] 3. Sort-Descending (cost) 4. i ← 1 5. while (i <= size(V)) 6. if W[i] <= M 7. M ← M – W[i] 8. total ← total + V[i]; 9. if W[i] > M 10. i ← i+1
Złożoność algorytmu:
- Jeżeli użyjemy prostego algorytmu sortowania (selekcja, bąbelkowanie…), wówczas złożoność całego problemu wynosi O(n2).
- Jeśli użyjemy sortowania szybkiego lub sortowania przez scalanie, złożoność całego problemu będzie wynosić O(nlogn).
Java kod dla Greedy Three
- Najpierw definiujesz klasę KnapsackPackage. Klasa ta posiada następujące właściwości: waga, wartość i odpowiadający jej koszt każdego opakowania. Koszt właściwości tej klasy służy do sortowania zadania w głównym algorytmie. Wartość każdego kosztu wynosi
stosunek każdego opakowania.
public class KnapsackPackage {
private double weight;
private double value;
private Double cost;
public KnapsackPackage(double weight, double value) {
super();
this.weight = weight;
this.value = value;
this.cost = new Double(value / weight);
}
public double getWeight() {
return weight;
}
public double getValue() {
return value;
}
public Double getCost() {
return cost;
}
}
- Następnie tworzysz funkcję wykonującą algorytm Greedy Three.
public void knapsackGreProc(int W[], int V[], int M, int n) {
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int i = 0; i < n; i ++) {
packs[i] = new KnapsackPackage(W[i], V[i]);
}
Arrays.sort(packs, new Comparator<KnapsackPackage>() {
@Override
public int compare(KnapsackPackage kPackA, KnapsackPackage kPackB) {
return kPackB.getCost().compareTo(kPackA.getCost());
}
});
int remain = M;
double result = 0d;
int i = 0;
boolean stopProc = false;
while (!stopProc) {
if (packs[i].getWeight() <= remain) {
remain -= packs[i].getWeight();
result += packs[i].getValue();
System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue());
}
if (packs[i].getWeight() > remain) {
i ++;
}
if (i == n) {
stopProc = true;
}
}
System.out.println("Max Value:\t" + result);
}
Wyjaśnienie kodu:
- Zainicjuj wagę i wartość każdego opakowania plecakowego.
- Sortuj paczki plecakowe według kosztu w kolejności malejącej.
- Jeśli wybierzesz pakiet I.
- Jeśli wybierzesz liczbę pakietów, wystarczy.
- Zatrzymaj się podczas przeglądania wszystkich pakietów.
W tym samouczku masz dwa przykłady. Oto kod Java do uruchomienia powyższego programu z dwoma przykładami:
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{15, 10, 2, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{30, 25, 2, 6};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 37;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
Masz dane wyjściowe:
- Pierwszy przykład:
Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0
- Drugi przykład:
Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0
Przeanalizuj pierwszy przykład:
- Parametry problemu to: n = 4; M = 37.
- Pakiety: {i = 1; W[i] = 15; V[i] = 30; Koszt = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Koszt = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Koszt = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Koszt = 1.5}.
- Przesyłki sortujesz według kolejności nie zwiększania wartości kosztów jednostkowych. Masz: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
Kroki zastosowania algorytmu dla pierwszego przykładu:
- Zdefiniuj x1, x2, x3, x4 to numer każdego wybranego pakietu, odpowiadający pakietowi {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
- Katalog główny węzła N reprezentuje stan, w którym nie wybrano żadnego pakietu. Następnie:
- Wartość całkowita = 0.
- M = 37 (zgodnie z propozycją).
- UpperBound = 37 * 2.5 = 92.5, z czego 37 to M, a 2.5 to koszt jednostkowy opakowania {i = 2}.
- Z pakietem {i = 2} masz 4 możliwości: wybierz 3 pakiety {i = 2} (x1 = 3); wybierz 2 pakiety {i = 2} (x1 = 2); wybierz 1 pakiet {i = 2} (x1 = 1) i nie wybieraj pakietu {i = 2} (x1 = 0). Zgodnie z tymi 4 możliwościami, rozgałęziasz węzeł główny N na 4 potomków N[1], N[2], N[3] i N[4].
- Dla węzła podrzędnego N1 masz:
- TotalValue = 0 + 3 * 25 = 75, gdzie 3 to numer wybranego pakietu {i = 2}, a 25 to wartość każdego pakietu {i = 2}.
- M = 37 – 3 * 10 = 7, gdzie 37 to początkowa ilość plecaka, 3 to numer paczki {i = 2}, 10 to waga każdej paczki {i = 2}.
- UpperBound = 75 + 7 * 2 = 89, gdzie 75 to TotalValue, 7 to pozostała waga plecaka, a 2 to koszt jednostkowy paczki {i = 1}.
- W podobny sposób można obliczyć parametry dla węzłów N[2], N[3] i N[4], w których UpperBound wynosi odpowiednio 84, 79 i 74.
- Spośród węzłów N[1], N[2], N[3] i N[4] węzeł N[1] ma największą granicę UpperBound, więc najpierw rozgałęzisz węzeł N[1] w nadziei, że będzie dobry plan z tej strony.
- Z węzła N[1] masz tylko jeden węzeł potomny N[1-1] odpowiadający x2 = 0 (ponieważ pozostała waga plecaka wynosi 7, podczas gdy waga każdej paczki {i = 1} wynosi 15) . Po określeniu parametrów przycisku N[1-1] górna granica N[1-1] wynosi 85.5.
- Kontynuujesz rozgałęzianie węzła N[1-1]. Węzeł N[1-1] ma 2 dzieci N[1-1-1] i N[1-1-2] odpowiadające x3 = 1 i x3 = 0. Po określeniu parametrów dla tych dwóch węzłów widać, że Górna granica N[1-1-1] wynosi 84, a granica N[1-1-2] wynosi 82, zatem kontynuujemy rozgałęzianie węzła N[1-1-1].
- Węzeł N[1-1-1] ma dwójkę dzieci, N[1-1-1-1] i N[1-1-1-2], co odpowiada x4 = 1 i x4 = 0. Są to dwa węzły-liście (reprezentujący opcję), ponieważ dla każdego węzła została wybrana liczba pakietów. W którym węzeł N[1-1-1-1] reprezentuje opcję x1 = 3, x2 = 0, x3 = 1 i x4 = 1 dla 83, natomiast węzeł N[1-1-1-2] reprezentuje opcję x1 = 3, x2 = 0, x3 = 1 i x4 = 01 przy 81. Zatem tymczasowa wartość maksymalna wynosi tutaj 83.
- Wracając do węzła N[1-1-2], widzisz, że UpperBound N[1-1-2] wynosi 82 < 83, więc przycinasz węzeł N[1-1-2].
- Wracając do węzła N2, widzisz, że UpperBound N2 wynosi 84 > 83, więc kontynuujesz rozgałęzianie węzła N2. Węzeł N2 ma dwoje dzieci N[2-1] i N[2-2] odpowiadających x2 = 1 i x2 = 0. Po obliczeniu parametrów dla N[2-1] i N[2-2] widać górna granica N[2-1] wynosi 83, a granica N[2-2] wynosi 75.25. Żadna z tych wartości nie jest większa niż 83, więc oba węzły zostaną przycięte.
- Na koniec przycinane są również węzły N3 i N4.
- Zatem wszystkie węzły na drzewie są rozgałęzione lub przycięte, więc najlepszym rozwiązaniem tymczasowym jest to, którego należy szukać. W związku z tym należy wybrać 3 paczki {i = 2}, 1 paczkę {i = 4} i jedną paczkę {i = 3} o łącznej wartości 83, łączna waga wynosi 36.
Po tej samej analizie drugiego przykładu otrzymasz wynik: wybierz pakiet 4 (3 razy) i pakiet 5 (3 razy).
Python3 kod dla Chciwej Trójki
- Najpierw definiujesz klasę KnapsackPackage.
class KnapsackPackage(object):
""" Knapsack Package Data Class """
def __init__(self, weight, value):
self.weight = weight
self.value = value
self.cost = value / weight
def __lt__(self, other):
return self.cost < other.cost
- Następnie tworzysz funkcję wykonującą algorytm Greedy Three.
class FractionalKnapsack(object):
def __init__(self):
def knapsackGreProc(self, W, V, M, n):
packs = []
for i in range(n):
packs.append(KnapsackPackage(W[i], V[i]))
packs.sort(reverse = True)
remain = M
result = 0
i = 0
stopProc = False
while (stopProc != True):
if (packs[i].weight <= remain):
remain -= packs[i].weight;
result += packs[i].value;
print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
if (packs[i].weight > remain):
i += 1
if (i == n):
stopProc = True
print("Max Value:\t", result)
Wyjaśnienie kodu:
- Zainicjuj wagę i wartość każdego opakowania plecakowego.
- Sortuj paczki plecakowe według kosztu w kolejności malejącej.
- Jeśli wybierzesz pakiet I.
- Jeśli wybierzesz liczbę pakietów, wystarczy.
- Zatrzymaj się podczas przeglądania wszystkich pakietów.
Oto Python3 kod do uruchomienia powyższego programu z pierwszym przykładem:
if __name__ == "__main__":
W = [15, 10, 2, 4]
V = [30, 25, 2, 6]
M = 37
n = 4
proc = FractionalKnapsack()
proc.knapsackGreProc(W, V, M, n)
Masz dane wyjściowe:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Kod C# dla Greedy Three
- Najpierw definiujesz klasę KnapsackPackage.
using System;
namespace KnapsackProblem
{
public class KnapsackPackage
{
private double weight;
private double value;
private double cost;
public KnapsackPackage(double weight, double value)
{
this.weight = weight;
this.value = value;
this.cost = (double) value / weight;
}
public double Weight
{
get { return weight; }
}
public double Value
{
get { return value; }
}
public double Cost
{
get { return cost; }
}
}
}
- Następnie tworzysz funkcję wykonującą algorytm Greedy Three.
using System;
namespace KnapsackProblem
{
public class FractionalKnapsack
{
public FractionalKnapsack()
{
}
public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int k = 0; k < n; k++)
packs[k] = new KnapsackPackage(W[k], V[k]);
Array.Sort<KnapsackPackage>(packs, new Comparison<KnapsackPackage>(
(kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost)));
double remain = M;
double result = 0d;
int i = 0;
bool stopProc = false;
while (!stopProc)
{
if (packs[i].Weight <= remain)
{
remain -= packs[i].Weight;
result += packs[i].Value;
Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value);
}
if (packs[i].Weight > remain)
{
i++;
}
if (i == n)
{
stopProc = true;
}
}
Console.WriteLine("Max Value:\t" + result);
}
}
}
Wyjaśnienie kodu:
- Zainicjuj wagę i wartość każdego opakowania plecakowego.
- Sortuj paczki plecakowe według kosztu w kolejności malejącej.
- Jeśli wybierzesz pakiet I.
- Jeśli wybierzesz liczbę pakietów, wystarczy.
- Zatrzymaj się podczas przeglądania wszystkich pakietów.
Oto kod C# do uruchomienia powyższego programu z pierwszym przykładem:
public void run()
{
/*
* Pack and Weight - Value
*/
int[] W = new int[]{15, 10, 2, 4};
//int[] W = new int[] { 12, 2, 1, 1, 4 };
int[] V = new int[]{30, 25, 2, 6};
//int[] V = new int[] { 4, 2, 1, 2, 10 };
/*
* Max Weight
*/
int M = 37;
//int M = 15;
int n = V.Length;
/*
* Run the algorithm
*/
KnapsackGreProc(W, V, M, n);
}
Masz dane wyjściowe:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Kontrprzykład Chciwej Trójki
Algorytm Greedy Three rozwiązuje się szybko i w niektórych przypadkach może być również optymalny. Jednak w niektórych szczególnych przypadkach nie daje to optymalnego rozwiązania. Tutaj masz kontrprzykład:
- Parametry problemu to: n = 3; M = 10.
- Pakiety: {i = 1; W[i] = 7; V[i] = 9; Koszt = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Koszt = 1}; {i = 3; W[i] = 4; V[i] = 4; Koszt = 1}.
- Algorytm wybierze (pakiet 1) o łącznej wartości 9, natomiast optymalnym rozwiązaniem problemu będzie (pakiet 2, pakiet 3) o łącznej wartości 10.
Oto kod Java do uruchomienia powyższego programu z kontrprzykładem:
public void run() {
/*
* Pack and Weight - Value
*/
int W[] = new int[]{7, 6, 4};
int V[] = new int[]{9, 6, 4};
/*
* Max Weight
*/
int M = 10;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
Oto wynik:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
To wszystko, jeśli chodzi o problem ułamkowego plecaka.
