I am trying to understand what the difference is between the fractional knapsack problem using dynamic programming, and the greedy solution version. Im looking at an example of the fractional problem which looks like:

enter image description here

What's the difference between that and the greedy solution? Are you not just taking the value-per-pound in this example too but it's just not explicitly stated?

  • $\begingroup$ The greedy solution to what? To fractional knapsack or regular knapsack? $\endgroup$ – David Richerby Mar 30 '17 at 7:43
  • $\begingroup$ What you mean by "the difference"? The two algorithms are very obviously not the same. $\endgroup$ – Raphael Apr 29 '17 at 8:30

The fractional Knapsack problem isn't solved using Dynamic Programming, but can be solved using a greedy algorithm. Item A is \$50/unit, B is \$5/unit and C is \$40/unit. The greedy method is to use as much of the highest value items as possible, which gives the solution on the image.

Dynamic Programming allows you to solve the problem when you cannot split the items.

| cite | improve this answer | |
  • $\begingroup$ "The fractional Knapsack problem isn't solved using Dynamic Programming" -- but it can solve it. $\endgroup$ – Raphael Apr 29 '17 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.