Optymalizacja dyskretna (w tym algorytmy heurystyczne)

class: center, middle, inverse, title-slide

.title[
# Optymalizacja dyskretna <br>(w tym algorytmy heurystyczne)
]
.subtitle[
## Programowanie dynamiczne
]
.author[
### Jakub Nowosad <br><a href="https://jakubnowosad.com/" class="uri">https://jakubnowosad.com/</a>
]

---

# Programowanie dynamiczne

- **Dynamic programming**
- Algorytm dokładny (nieheurystyczny) - wyszukiwanie optymalnego rozwiązania bez konieczności sprawdzania wszystkich rozwiązań
- Stosowane do wieloetapowych procesów decyzyjnych
- Programowanie dynamiczne opiera się na podziale rozwiązywanego problemu na podproblemy względem kilku parametrów
- Zasada optymalności Bellmana - decyzja optymalna podjęta w kroku `i` jest nadal optymalną w kroku `i+1` i kolejnych. (Nie możemy się cofać)
- Programowanie dynamiczne sprowadza się do rozbicia problemu optymalizacyjnego na prostsze podproblemy i zapisania rozwiązania każdego podproblemu tak, aby każdy podproblem został rozwiązany tylko raz

---
# Programowanie dynamiczne

- W programowaniu dynamicznym skracamy czas obliczeń kosztem zajmowanej przestrzeni (np. w pamięci)
- https://www.quora.com/How-should-I-explain-dynamic-programming-to-a-4-year-old/answer/Jonathan-Paulson:

> *writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper* <br>
"What's that equal to?" <br>
*counting* "Eight!" <br>
*writes down another "1+" on the left* <br>
"What about that?" <br>
*quickly* "Nine!" <br>
"How'd you know it was nine so fast?" <br>
"You just added one more" <br>
"So you didn't need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'"

---
# Programowanie dynamiczne

Dwa wymagania:

1. **Optymalna podstruktura** - rozwiązanie problemu optymalizacyjnego można określić poprzez optymalnie rozwiązanie jego podproblemów. 
2. **Nakładające się podproblemy** - każdy rekurencyjny algorytm rozwiązujący problem powinien rozwiązywać te same podproblemy w kółko, a nie generować nowe podproblemy.

W odróżnieniu od techniki dziel i zwyciężaj (ang. *divide and conquer*) podproblemy w programowaniu dynamicznym nie są rozłączne, ale musi je cechować własność optymalnej podstruktury.

---
# Programowanie dynamiczne

- Aby rozwiązać dany problem należy rozwiązać wszystkie problemy cząstkowe
- Tworzymy w ten sposób drzewo zależności (a nie regularne drzewo)

[Dwa podejścia](https://media.geeksforgeeks.org/wp-content/cdn-uploads/Tabulation-vs-Memoization-1.png):

- **Bottom-up** - rozwiązanie problemu rekurencyjnie poprzez rozwiązywanie najmniejszych podproblemów (**tabulation**)
- **Top-down** - by uniknąć wielokrotnego rozwiązywania identycznych problemów cząstkowych przechowujemy ich wyniki (redukujemy złożoność obliczeniową) (**memoization**, nie *memorization*!)

---
# Bottom-up Dynamic Programming

- Rozwiązujemy najpierw najmniejsze podproblemy
- Wykorzystujemy je rozwiązania do zbudowania i znalezienia rozwiązań dla większych podproblemów

---
# Top-down Dynamic Programming

- Zapamiętujemy rozwiązania do podproblemów
- Za każdym razem, gdy próbujemy rozwiązać nowy podproblem, najpierw sprawdzamy tabelę, czy jest już rozwiązany
- Jeśli rozwiązanie zostało zapisane, możemy użyć go bezpośrednio, w przeciwnym razie rozwiążemy podproblemy i dodamy ich rozwiązanie do tabeli

---
# Rekurencja

.pull-left[
<img src="images/serpiente.jpg" style="display: block; margin: auto;" />
]

.pull-right[
- *Recursion* - technika wykorzystywana w programowaniu polegająca do odwoływaniu się funkcji do samej siebie
- "To understand recursion, you must understand recursion."
- Przykład - wyliczanie silni:

```
unsigned int factorial(unsigned int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}
```

]

---
# Rekurencja

<div class="figure" style="text-align: center">
<img src="images/recursion.jpg" alt="https://www.smbc-comics.com/comic/recursion" width="60%" />
<p class="caption">https://www.smbc-comics.com/comic/recursion</p>
</div>

---
# Ciąg Fibonacciego

.pull-left[
- Taki ciąg liczb naturalnych, gdzie każdy kolejny wyraz jest sumą dwóch poprzednich, zaczynając od 0 i 1
- https://www.youtube.com/watch?v=SjSHVDfXHQ4, https://www.youtube.com/watch?v=kkGeOWYOFoA
- Przykład

$$
0, 1, 1, 2, 3, 5, 8, ...
$$

- Dla uproszczenia - nie zajmujemy się pierwszym 0 i 1

]

.pull-right[
<img src="images/fib.png" width="70%" style="display: block; margin: auto;" />

- Drzewo zależności
- Potwierdza ono, że jest to problem pasujący do programowania dynamicznego

]

---
# Ciąg Fibonacciego

https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence

Rekurencyjna funkcja do wyliczania wartości ciągu Fibonacciego:

```
function fib(n)
    if n <= 1 return n
    return fib(n − 1) + fib(n − 2)
```

Określenie wartości ciągu Fibonacciego:

1. `fib(5)`
2. `fib(4) + fib(3)`
3. `(fib(3) + fib(2)) + (fib(2) + fib(1))`
4. `((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))`
5. `(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))`

Jaki tutaj istnieje problem?

- **Część obliczeń jest wykonywanych wielokrotnie.**
- **Złożoność wykładnicza  (O(2<sup>n</sup>))**

---
# Ciąg Fibonacciego

Podejście **bottom-up**:

```
function fib(n)
    if n = 0
        return 0
    else
        var previousFib := 0, currentFib := 1
        repeat n − 1 times // loop is skipped if n = 1
            var newFib := previousFib + currentFib
            previousFib := currentFib
            currentFib  := newFib
    return currentFib
```

- Zaczynamy od wyliczenia najmniejszej wartości `fib`, a dopiero następnie coraz to wyższych wartości z tej wcześniej uzyskanej
- Złożoność liniowa (O(n))

---
# Ciąg Fibonacciego

Podejście **top-down**:

```
var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]
```

- **Memoization** - przechowujemy wartości już wykonanych obliczeń
- Złożoność liniowa (O(n))

---
# Problem wydawania reszty

https://www.cs.usfca.edu/~galles/visualization/DPChange.html

<div class="figure" style="text-align: center">
<img src="images/reszta.gif" alt="http://algorytmy.ency.pl/artykul/programowanie_dynamiczne" width="58%" />
<p class="caption">http://algorytmy.ency.pl/artykul/programowanie_dynamiczne</p>
</div>

---
# Schemat działania

1. **Określ czy problem można rozwiązać używając programowania dynamicznego**
2. **Ustal jak przedstawić stan używając jak najmniejszej liczby parametrów**
3. **Sformułuj relacje pomiędzy stanami**
4. **Użyj tabulacji lub memoizacji**

Inne podejście:
- https://www.quora.com/What-are-some-good-ways-to-approach-a-dynamic-programming-question/answer/Paul-Baltescu

---
# Schemat działania

1) **Określ czy problem można rozwiązać używając programowania dynamicznego**

- Zazwyczaj problemy, które wymagają zmaksymalizowania lub zminimalizowania pewnych ilości lub problemy z liczeniem, które mówią o wyliczaniu rozmieszczeń pod pewnymi warunkami mogą być rozwiązane za pomocą programowania dynamicznego

---
# Schemat działania

2) **Ustal jak przedstawić stan używając jak najmniejszej liczby parametrów**

- Problemy programowania dynamicznego dotyczą stanu i jego przejścia
- Stan - można zdefiniować jako zbiór parametrów, które w unikalny sposób identyfikują konkretną pozycję lub położenie w danym problemie.
Ten zestaw parametrów powinien być jak najmniejszy, aby zmniejszyć przestrzeń stanu
- W problemie plecakowym tymi parametrami mogą być indeks i waga

---
# Schemat działania

3) **Sformułuj relacje pomiędzy stanami**

- Przykład - https://www.geeksforgeeks.org/solve-dynamic-programming-problem/

---
# Schemat działania

4) **Użyj tabulacji lub memoizacji**

- Przykład - https://www.geeksforgeeks.org/solve-dynamic-programming-problem/

---
# Zastosowanie

- https://www.geeksforgeeks.org/dynamic-programming/
- https://blog.usejournal.com/top-50-dynamic-programming-practice-problems-4208fed71aa3

---
class: inverse, left, bottom
# Przykłady

<!--
Proces alokacyjny

http://www.cs.put.poznan.pl/arybarczyk/TeoriaAiSD3.pdf

- Jednowymiarowy proces alokacyjny
- Pierwszy wiersz przedstawia koszt (ile zasobu musimy wydać)
- Kolejne wiersze przedstawiają zyski dla różnych działalności
- Cel: podzielenie `M = 8` jednostek zasobu na `N = 3` działalności, tak aby maksymalizować zyski

<table>
<tbody>
  <tr>
   <td style="text-align:left;"> koszt </td>
   <td style="text-align:right;"> 0 </td>
   <td style="text-align:right;"> 1 </td>
   <td style="text-align:right;"> 2 </td>
   <td style="text-align:right;"> 3 </td>
   <td style="text-align:right;"> 4 </td>
   <td style="text-align:right;"> 5 </td>
   <td style="text-align:right;"> 6 </td>
   <td style="text-align:right;"> 7 </td>
   <td style="text-align:right;"> 8 </td>
  </tr>
  <tr>
   <td style="text-align:left;"> dzialalnosc1 </td>
   <td style="text-align:right;"> 0 </td>
   <td style="text-align:right;"> 5 </td>
   <td style="text-align:right;"> 15 </td>
   <td style="text-align:right;"> 40 </td>
   <td style="text-align:right;"> 80 </td>
   <td style="text-align:right;"> 90 </td>
   <td style="text-align:right;"> 95 </td>
   <td style="text-align:right;"> 98 </td>
   <td style="text-align:right;"> 100 </td>
  </tr>
  <tr>
   <td style="text-align:left;"> dzialalnosc2 </td>
   <td style="text-align:right;"> 0 </td>
   <td style="text-align:right;"> 5 </td>
   <td style="text-align:right;"> 15 </td>
   <td style="text-align:right;"> 40 </td>
   <td style="text-align:right;"> 60 </td>
   <td style="text-align:right;"> 70 </td>
   <td style="text-align:right;"> 73 </td>
   <td style="text-align:right;"> 74 </td>
   <td style="text-align:right;"> 75 </td>
  </tr>
  <tr>
   <td style="text-align:left;"> dzialalnosc3 </td>
   <td style="text-align:right;"> 0 </td>
   <td style="text-align:right;"> 4 </td>
   <td style="text-align:right;"> 26 </td>
   <td style="text-align:right;"> 40 </td>
   <td style="text-align:right;"> 45 </td>
   <td style="text-align:right;"> 50 </td>
   <td style="text-align:right;"> 51 </td>
   <td style="text-align:right;"> 52 </td>
   <td style="text-align:right;"> 53 </td>
  </tr>
</tbody>
</table>

Proces alokacyjny

- Co by było gdyby... Zaczynając od ostatniej decyzji (zajmujemy się ostatnią działalnością do wyboru)

<table>
<tbody>
  <tr>
   <td style="text-align:left;"> pozostaly_zasob </td>
   <td style="text-align:left;"> 0 </td>
   <td style="text-align:left;"> 1 </td>
   <td style="text-align:left;"> 2 </td>
   <td style="text-align:left;"> 3 </td>
   <td style="text-align:left;"> 4 </td>
   <td style="text-align:left;"> 5 </td>
   <td style="text-align:left;"> 6 </td>
   <td style="text-align:left;"> 7 </td>
   <td style="text-align:left;"> 8 </td>
  </tr>
  <tr>
   <td style="text-align:left;"> zysk3 </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
  </tr>
  <tr>
   <td style="text-align:left;"> koszt3 </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
  </tr>
  <tr>
   <td style="text-align:left;"> zysk2 </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
  </tr>
  <tr>
   <td style="text-align:left;"> koszt2 </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
  </tr>
  <tr>
   <td style="text-align:left;"> zysk1 </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
  </tr>
  <tr>
   <td style="text-align:left;"> koszt1 </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
  </tr>
</tbody>
</table>

Proces alokacyjny

- Co by było gdyby... Zaczynając od ostatniej decyzji (zajmujemy się ostatnią działalnością do wyboru)

<table>
<tbody>
  <tr>
   <td style="text-align:left;"> pozostaly_zasob </td>
   <td style="text-align:left;"> 0 </td>
   <td style="text-align:left;"> 1 </td>
   <td style="text-align:left;"> 2 </td>
   <td style="text-align:left;"> 3 </td>
   <td style="text-align:left;"> 4 </td>
   <td style="text-align:left;"> 5 </td>
   <td style="text-align:left;"> 6 </td>
   <td style="text-align:left;"> 7 </td>
   <td style="text-align:left;"> 8 </td>
  </tr>
  <tr>
   <td style="text-align:left;"> zysk3 </td>
   <td style="text-align:left;"> 0 </td>
   <td style="text-align:left;"> 4 </td>
   <td style="text-align:left;"> 26 </td>
   <td style="text-align:left;"> 40 </td>
   <td style="text-align:left;"> 45 </td>
   <td style="text-align:left;"> 50 </td>
   <td style="text-align:left;"> 51 </td>
   <td style="text-align:left;"> 52 </td>
   <td style="text-align:left;"> 53 </td>
  </tr>
  <tr>
   <td style="text-align:left;"> koszt3 </td>
   <td style="text-align:left;"> 0 </td>
   <td style="text-align:left;"> 1 </td>
   <td style="text-align:left;"> 2 </td>
   <td style="text-align:left;"> 3 </td>
   <td style="text-align:left;"> 4 </td>
   <td style="text-align:left;"> 5 </td>
   <td style="text-align:left;"> 6 </td>
   <td style="text-align:left;"> 7 </td>
   <td style="text-align:left;"> 8 </td>
  </tr>
  <tr>
   <td style="text-align:left;"> zysk2 </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
  </tr>
  <tr>
   <td style="text-align:left;"> koszt2 </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
  </tr>
  <tr>
   <td style="text-align:left;"> zysk1 </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
  </tr>
  <tr>
   <td style="text-align:left;"> koszt1 </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
   <td style="text-align:left;">  </td>
  </tr>
</tbody>
</table>

-->

---
# Problem plecakowy I

- http://www.cs.put.poznan.pl/mkasprzak/zp/ZP-wyklad5.pdf
- `$I = 5$`, `$W = 10$`, `$c_i = [3, 4, 2, 6, 1]$`, `$w_i = [5, 3, 2, 4, 3]$`

Tablica programowania dynamicznego:

<div class="datatables html-widget html-fill-item-overflow-hidden html-fill-item" id="htmlwidget-46961d02ca5b860589d2" style="width:100%;height:auto;"></div>
<script type="application/json" data-for="htmlwidget-46961d02ca5b860589d2">{"x":{"filter":"none","vertical":false,"data":[["0","1","2","3","4","5"],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,2,2,2],[0,0,4,4,4,4],[0,0,4,4,6,6],[0,3,4,6,6,6],[0,3,4,6,8,8],[0,3,4,6,10,10],[0,3,7,7,10,10],[0,3,7,7,12,12],[0,3,7,9,12,12]],"container":"<table class=\"display\">\n  <thead>\n    <tr>\n      <th> <\/th>\n      <th>0<\/th>\n      <th>1<\/th>\n      <th>2<\/th>\n      <th>3<\/th>\n      <th>4<\/th>\n      <th>5<\/th>\n      <th>6<\/th>\n      <th>7<\/th>\n      <th>8<\/th>\n      <th>9<\/th>\n      <th>10<\/th>\n    <\/tr>\n  <\/thead>\n<\/table>","options":{"dom":"t","columnDefs":[{"className":"dt-right","targets":[1,2,3,4,5,6,7,8,9,10,11]},{"orderable":false,"targets":0}],"order":[],"autoWidth":false,"orderClasses":false}},"evals":[],"jsHooks":[]}</script>

---
# Problem plecakowy I

- http://www.cs.put.poznan.pl/mkasprzak/zp/ZP-wyklad5.pdf
- `$I = 5$`, `$W = 10$`, `$c_i = [3, 4, 2, 6, 1]$`, `$w_i = [5, 3, 2, 4, 3]$`
- Rozwiązanie odczytujemy od końca, cofając się z pola `$(I,W)$` po kolei do pól, z których wyprowadzone zostały wartości składające się na optymalną
ścieżkę.
Kończymy na wartości 0.

<div class="datatables html-widget html-fill-item-overflow-hidden html-fill-item" id="htmlwidget-7e980a96297777cd3cb7" style="width:100%;height:auto;"></div>
<script type="application/json" data-for="htmlwidget-7e980a96297777cd3cb7">{"x":{"filter":"none","vertical":false,"data":[["0","1","2","3","4","5"],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,2,2,2],[0,0,4,4,4,4],[0,0,4,4,6,6],[0,3,4,6,6,6],[0,3,4,6,8,8],[0,3,4,6,10,10],[0,3,7,7,10,10],[0,3,7,7,12,12],[0,3,7,9,12,12]],"container":"<table class=\"display\">\n  <thead>\n    <tr>\n      <th> <\/th>\n      <th>0<\/th>\n      <th>1<\/th>\n      <th>2<\/th>\n      <th>3<\/th>\n      <th>4<\/th>\n      <th>5<\/th>\n      <th>6<\/th>\n      <th>7<\/th>\n      <th>8<\/th>\n      <th>9<\/th>\n      <th>10<\/th>\n    <\/tr>\n  <\/thead>\n<\/table>","options":{"dom":"t","columnDefs":[{"targets":5,"render":"function(data, type, row, meta) {\n    return type !== 'display' ? data : DTWidget.formatRound(data, 0, 3, \",\", \".\", null);\n  }"},{"targets":2,"render":"function(data, type, row, meta) {\n    return type !== 'display' ? data : DTWidget.formatRound(data, 0, 3, \",\", \".\", null);\n  }"},{"className":"dt-right","targets":[1,2,3,4,5,6,7,8,9,10,11]},{"orderable":false,"targets":0}],"order":[],"autoWidth":false,"orderClasses":false,"rowCallback":"function(row, data, displayNum, displayIndex, dataIndex) {\nvar value=data[11]; $(this.api().cell(row, 11).node()).css({'background':value == 12 ? \"lightblue\" : null});\nvar value=data[7]; $(this.api().cell(row, 7).node()).css({'background':value == 6 ? \"lightblue\" : null});\nvar value=data[5]; $(this.api().cell(row, 5).node()).css({'background':value == 4.01 ? \"lightblue\" : null});\nvar value=data[2]; $(this.api().cell(row, 2).node()).css({'background':value == 0.01 ? \"lightblue\" : null});\n}"}},"evals":["options.columnDefs.0.render","options.columnDefs.1.render","options.rowCallback"],"jsHooks":[]}</script>

- **Rozwiązanie:** {2, 3, 4}

---
# Problem plecakowy II

- https://www.hackerearth.com/practice/notes/the-knapsack-problem/ 
- https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

---
# Problem komiwojażera

- https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm
- https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/
- https://towardsdatascience.com/solving-tsp-using-dynamic-programming-2c77da86610d

---
class: inverse, left, bottom
# Inne materiały

---
# Inne materiały

- https://www.youtube.com/watch?v=B_SpfyPl5XA
- https://cran.r-project.org/web/packages/RcppDynProg/vignettes/Segmentation.html
- https://www.geeksforgeeks.org/dynamic-programming/
- https://github.com/llSourcell/dynamic_programming/blob/master/Dynamic%20Programming.ipynb
- https://www.hackerearth.com/practice/notes/dynamic-programming-i-1/
- https://blog.usejournal.com/top-50-dynamic-programming-practice-problems-4208fed71aa3
- https://medium.com/basecs/speeding-up-the-traveling-salesman-using-dynamic-programming-b76d7552e8dd
- https://dev.to/victoria/knapsack-problem-algorithms-for-my-real-life-carry-on-knapsack-33jj
- Błażewicz, Jacek (1983) Badania operacyjne dla informatyków, Wydaw. Nauk.-Techn., Warszawa
- http://www.micsymposium.org/mics_2005/papers/paper102.pdf