About knapsack problem the most important thing is that, you have to reorder the objects in descending order of profit per capacity or (Pi/Wi). When the reordering is done, then you can select the object one by one following that order. And it is guaranteed that order will produce the optimal solution for your knapsack problem. Here is the wiki link you want to read:
http://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm
No comments:
Post a Comment