-1

Knapsack problem we can solve several methods:

  • dynamic programming

  • branch and bound

  • greedy method

  • genetic algorithm

  • Brute force

  • Heuristic by the value / size

Which of these methods gives accurate results? or all methods give only approximate results?

Miska Hincova
  • 13
  • I've used linear programming techniques in Excel and implemented the Hungarian Algorithm in java and C to solve this problem. Both techniques worked well. The solutions provided were the closest possible to a perfect solution assuming items being placed into the backpack are not divisible into smaller equivalents. – mba12 May 23 '16 at 19:51

1 Answers1

2

Dynamic programming and branch and bound give accurate answer by definition.

Greedy algorithm gives inaccurate answer, but it is fast. Brute force gives an accurate solution, but has really bad complexity ($O(n!)$).

All the other methods are inaccurate. But everything depends on where to implement these algorithms. If you are solving programming task on TopCoder, you'll possibly use some sort of dynamic programming with its accurate answer and okay complexity. But if you're solving a real life problem with really large input, you'll possibly use optimization (genetic, for example). If the input is tiny, bruteforce works.

sooobus
  • 710