Program Dinamis
Memiliki lebih banyak keputusan, tidak seperti algoritma Greedy yang hanya memiliki 1 keputusan dan belum tentu optimal
Mundur:
Tahap 4
| s | f4(s) (total cost) | X4 (nyampe ke) |
|---|---|---|
| 8 | 3 | 10 |
| 9 | 4 | 10 |
| Tahap 3 |
| s | 8 | 9 | f3(s) (min cost) | X3 (nyampe ke) |
|---|---|---|---|---|
| 5 | 1+3 = 4 | 4+4 = 8 | 4 | 8 |
| 6 | 9 | 7 | 7 | 9 |
| 7 | 6 | 7 | 6 | 8 |
| Tahap 2 |
| s | 5 | 6 | 7 | f2(s) (min cost) | X2 (nyampe ke) |
|---|---|---|---|---|---|
| 2 | 7+4 = 11 | 4+7 = 11 | 12 | 11 | 5 atau 6 |
| 3 | 3+4 = 7 | 9 | 10 | 7 | 5 |
| 4 | 8 | 8 | 11 | 8 | 5 atau 6 |
| Tahap 1 |
| s | 2 | 3 | 4 | f1(s) | X1 |
|---|---|---|---|---|---|
| 1 | 2+11 = 13 | 11 | 11 | 11 | 3 atau 4 |
Maju
Contoh untuk Knapsack 0/1
Tahap 1 - Item 1 (Weight = 2, Profit = 65)
| y | f0(y) | 65 + f0(y-2) | f1(y) | (x1, x2, x3) |
|---|---|---|---|---|
| 0 | 0 | 0 | (0,0,0) | |
| 1 | 0 | 0 | (0,0,0) | |
| 2 | 0 | 65 + 0 | 65 | (1,0,0) |
| 3 | 0 | 65 + 0 | 65 | (1,0,0) |
| 4 | 0 | 65 + 0 | 65 | (1,0,0) |
| 5 | 0 | 65 + 0 | 65 | (1,0,0) |
| Tahap 2 - Item 2 (Weight = 3, Profit = 80) |
| y | f1(y) | 80 + f1(y-3) | f2(y) | (x1, x2, x3) |
|---|---|---|---|---|
| 0 | 0 | 0 | (0,0,0) | |
| 1 | 0 | 0 | (0,0,0) | |
| 2 | 65 | 65 | (1,0,0) | |
| 3 | 65 | 80 | 80 | (0,1,0) |
| 4 | 65 | 80 | 80 | (0,1,0) |
| 5 | 65 | 80+65 = 145 | 145 | (1,1,0) |
| Tahap 3 - Item 3 (Weight = 1, Profit = 30) |
| y | f2(y) | 30 + f2(y-3) | f3(y) | (x1, x2, x3) |
|---|---|---|---|---|
| 0 | 0 | 0 | (0,0,0) | |
| 1 | 0 | 30+0 | 30 | (0,0,1) |
| 2 | 65 | 30+0 | 65 | (1,0,0) |
| 3 | 80 | 30+65 | 95 | (1,0,1) |
| 4 | 80 | 30+80 | 110 | (0,1,1) |
| 5 | 145 | 30+80 | 145 | (1,1,0) |