Comparison between two algorithms solving fractional knapsack

1
votes

I have written the fractional knapsack problem with two algorithms (Greedy and dynamic programming algorithm) and I have to make a comparison between them .. I only made a comparison in terms of time and space complexity .. I have no idea about what additional factors can be used for making comparison between the two algorithms.. I hope that anyone could help me and provides me with any idea .

1
dynamiccomparisonknapsack-problemgreedy
Please provide a definition of "fractional knapsack"; if it is a problem formulation where items can be chosen partly, it is not necessary to use dynamic programming but can be solved in O(n log n) time by sorting. – Codor

1 Answers

0
votes

Although the question is a bit broadly asked, different criteria for comparison might include:

  • actual running time vs. instance quality, i.e. relative gap to an optimal solution
  • implementation difficulty

As practical evaluation of algorithms is an involved subject, I suggest reading A Theoretician's Guide to the Experimental Analysis of Algorithms by Johnson to avoid some common pitfalls and misconceptions.