Skip to content

Latest commit

 

History

History
220 lines (218 loc) · 4.43 KB

README.md

File metadata and controls

220 lines (218 loc) · 4.43 KB

2. 0-1 knapsack problem

  • Dynamic programming algorithm
  • Approximation algorithms
    • 2-Approximation
    • FPTAS
  • Least Cost B&B algorithm
data algorithm price weight time per 100k rep., s interim solutions
p01 DP 309 165 4.54887 1650
2-Approx 309 165 0.249447 11
FPTAS 309 165 4.41283 1660
B&B 309 165 2.30782 32
p02 DP 51 26 0.557674 130
2-Approx 47 23 0.165083 6
FPTAS 51 26 0.605311 135
B&B 51 26 0.711793 10
p03 DP 150 190 3.06968 1140
2-Approx 146 179 0.18163 7
FPTAS 150 190 3.12938 1146
B&B 150 190 1.56472 24
p04 DP 107 50 1.23409 350
2-Approx 97 45 0.204052 8
FPTAS 107 50 1.29945 357
B&B 107 50 1.45545 24
p05 DP 900 104 2.68133 832
2-Approx 770 65 0.223181 9
FPTAS 870 85 2.56241 840
B&B 900 104 1.63623 21
p06 DP 1735 169 3.24566 1190
2-Approx 1478 140 0.215007 8
FPTAS 1735 169 3.3237 1197
B&B 1735 169 3.32812 58
p07 DP 1458 749 31.5543 11250
2-Approx 1441 740 0.519255 16
FPTAS 1458 749 31.5029 11265
B&B 1458 749 97.2301 1058