The research work on Knapsack Problem algorithms
benchmarks: https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html
- capacity: 165
- optimal solution:
[1, 1, 1, 1, 0, 1, 0, 0, 0, 0] - optimal weight: 165, and profit: 309
BruteForce optimal solution:[1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
optimal weight: 165, and profit 309
Greedy optimal solution:[1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
optimal weight: 165, and profit 309
Branch-And-Bound optimal solution:[1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
optimal weight: 165, and profit 309
Dynamic optimal solution:[1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
optimal weight: 165, and profit 309
Genetic optimal solution:[1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
optimal weight: 165, and profit 309
- capacity: 26
- optimal solution:
[0, 1, 1, 1, 0] - optimal weight: 26, and profit: 51
BruteForce optimal solution:[0, 1, 1, 1, 0]
optimal weight: 26, and profit 51
Greedy optimal solution:[1, 0, 1, 0, 0]
optimal weight: 23, and profit 47
Branch-And-Bound optimal solution:[0, 1, 1, 1, 0]
optimal weight: 26, and profit 51
Dynamic optimal solution:[0, 1, 1, 1, 0]
optimal weight: 26, and profit 51
Genetic optimal solution:[0, 1, 1, 1, 0]
optimal weight: 26, and profit 51
- capacity: 190
- optimal solution:
[1, 1, 0, 0, 1, 0] - optimal weight: 190, and profit: 150
BruteForce optimal solution:[1, 1, 0, 0, 1, 0]
optimal weight: 190, and profit 150
Greedy optimal solution:[1, 1, 0, 1, 0, 0]
optimal weight: 179, and profit 146
Branch-And-Bound optimal solution:[1, 1, 0, 0, 1, 0]
optimal weight: 190, and profit 150
Dynamic optimal solution:[1, 1, 0, 0, 1, 0]
optimal weight: 190, and profit 150
Genetic optimal solution:[1, 0, 1, 0, 0, 1]
optimal weight: 153, and profit 119
- capacity: 50
- optimal solution:
[1, 0, 0, 1, 0, 0, 0] - optimal weight: 50, and profit: 107
BruteForce optimal solution:[1, 0, 0, 1, 0, 0, 0]
optimal weight: 50, and profit 107
Greedy optimal solution:[1, 1, 0, 0, 1, 1, 0]
optimal weight: 48, and profit 102
Branch-And-Bound optimal solution:[1, 0, 0, 1, 0, 0, 0]
optimal weight: 50, and profit 107
Dynamic optimal solution:[1, 0, 0, 1, 0, 0, 0]
optimal weight: 50, and profit 107
Genetic optimal solution:[1, 1, 0, 0, 0, 1, 1]
optimal weight: 50, and profit 105
- capacity: 104
- optimal solution:
[1, 0, 1, 1, 1, 0, 1, 1] - optimal weight: 104, and profit: 900
BruteForce optimal solution:[1, 0, 1, 1, 1, 0, 1, 1]
optimal weight: 104, and profit 900
Greedy optimal solution:[1, 1, 0, 1, 1, 1, 1, 1]
optimal weight: 97, and profit 858
Branch-And-Bound optimal solution:[1, 0, 1, 1, 1, 0, 1, 1]
optimal weight: 104, and profit 900
Dynamic optimal solution:[1, 0, 1, 1, 1, 0, 1, 1]
optimal weight: 104, and profit 900
Genetic optimal solution:[1, 0, 1, 1, 1, 0, 1, 1]
optimal weight: 104, and profit 900
- capacity: 170
- optimal solution:
[0, 1, 0, 1, 0, 0, 1] - optimal weight: 169, and profit: 1735
BruteForce optimal solution:[0, 1, 0, 1, 0, 0, 1]
optimal weight: 169, and profit 1735
Greedy optimal solution:[1, 1, 1, 0, 0, 0, 0]
optimal weight: 140, and profit 1478
Branch-And-Bound optimal solution:[0, 1, 0, 1, 0, 0, 1]
optimal weight: 169, and profit 1735
Dynamic optimal solution:[0, 1, 0, 1, 0, 0, 1]
optimal weight: 169, and profit 1735
Genetic optimal solution:[0, 1, 0, 1, 0, 0, 1]
optimal weight: 169, and profit 1735
- capacity: 750
- optimal solution:
[1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1] - optimal weight: 749, and profit: 1458
BruteForce optimal solution:[1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]
optimal weight: 749, and profit 1458
Greedy optimal solution:[1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]
optimal weight: 740, and profit 1441
Branch-And-Bound optimal solution:[1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]
optimal weight: 749, and profit 1458
Dynamic optimal solution:[1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]
optimal weight: 749, and profit 1458
Genetic optimal solution:[1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]
optimal weight: 749, and profit 1458
| benchmark | algorithm | execution mean | execution std | capacity | optim_weight | optim_profit |
|---|---|---|---|---|---|---|
| 1 | Branch-And-Bound | 0 | 0 | 165 | 165 | 309 |
| 1 | BruteForce | 0.0016 | 0.0005 | 165 | 165 | 309 |
| 1 | Dynamic | 0.006 | 0.0007 | 165 | 165 | 309 |
| 1 | Genetic | 0.0145 | 0.0089 | 165 | 165 | 309 |
| 1 | Greedy | 0 | 0 | 165 | 165 | 309 |
| 2 | Branch-And-Bound | 0 | 0 | 26 | 26 | 51 |
| 2 | BruteForce | 0 | 0 | 26 | 26 | 51 |
| 2 | Dynamic | 0.0006 | 0.0005 | 26 | 26 | 51 |
| 2 | Genetic | 0.0004 | 0.0005 | 26 | 24 | 47 |
| 2 | Greedy | 0 | 0 | 26 | 23 | 47 |
| 3 | Branch-And-Bound | 0.0002 | 0.0005 | 190 | 190 | 150 |
| 3 | BruteForce | 0 | 0 | 190 | 190 | 150 |
| 3 | Dynamic | 0.0044 | 0.0006 | 190 | 190 | 150 |
| 3 | Genetic | 0.0004 | 0.0005 | 190 | 172 | 119 |
| 3 | Greedy | 0 | 0 | 190 | 179 | 146 |
| 4 | Branch-And-Bound | 0 | 0 | 50 | 50 | 107 |
| 4 | BruteForce | 0.0006 | 0.0005 | 50 | 50 | 107 |
| 4 | Dynamic | 0.0012 | 0.0004 | 50 | 50 | 107 |
| 4 | Genetic | 0.0014 | 0.0009 | 50 | 50 | 107 |
| 4 | Greedy | 0 | 0 | 50 | 48 | 102 |
| 5 | Branch-And-Bound | 0 | 0 | 104 | 104 | 900 |
| 5 | BruteForce | 0.0004 | 0.0005 | 104 | 104 | 900 |
| 5 | Dynamic | 0.0038 | 0.0008 | 104 | 104 | 900 |
| 5 | Genetic | 0.0032 | 0.0008 | 104 | 103 | 898 |
| 5 | Greedy | 0 | 0 | 104 | 97 | 858 |
| 6 | Branch-And-Bound | 0.0002 | 0.0004 | 170 | 169 | 1735 |
| 6 | BruteForce | 0.0002 | 0.0005 | 170 | 169 | 1735 |
| 6 | Dynamic | 0.0052 | 0.0008 | 170 | 169 | 1735 |
| 6 | Genetic | 0.001 | 0.0007 | 170 | 169 | 1735 |
| 6 | Greedy | 0 | 0 | 170 | 140 | 1478 |
| 7 | Branch-And-Bound | 0.0042 | 0.0008 | 750 | 749 | 1458 |
| 7 | BruteForce | 0.0541 | 0.0147 | 750 | 749 | 1458 |
| 7 | Dynamic | 0.058 | 0.0047 | 750 | 749 | 1458 |
| 7 | Genetic | 0.306 | 0.0365 | 750 | 749 | 1458 |
| 7 | Greedy | 0.0002 | 0.0004 | 750 | 740 | 1441 |