Skip to content

Latest commit

 

History

History
164 lines (147 loc) · 9.79 KB

README.md

File metadata and controls

164 lines (147 loc) · 9.79 KB
Raw

KnapsackProblem

The research work on Knapsack Problem algorithms
benchmarks: https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html

Knapsack 01

  • 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

Knapsack 02

  • 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

Knapsack 03

  • 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

Knapsack 04

  • 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

Knapsack 05

  • 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

Knapsack 06

  • 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

Knapsack 07

  • 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

Comparison:

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