0
$\begingroup$

I am required to show that using the obvious greedy algorithm (which I'm assuming is the approach of choosing the highest value-by-weight items first) to solve the Knapsack problem yields a result that is greater than half of the optimal value. I'm unsure about how to go about solving this. Any help would be appreciated. Also, the question mentions using the "obvious" greedy algorithm which I assume is what I described in the parentheses above. Is this a correct assumption to make?

$\endgroup$
1
$\begingroup$

You will find a detailed proof https://courses.engr.illinois.edu/cs598csc/sp2009/Lectures/lecture_4.pdf

$\endgroup$

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.