Notice, that the above example does not even give that. The algorithm from previous step can be modified a bit to ensure at least 1/2 of value of the optimal solution. The optimal solution is taking Item 2′ of $40 of value. Because the next item, Item 2′, weighs too much to bring along. That would only result in taking Item 1′ of 1 kg and value $20. The above algorithm would order it by Item 1′ (15 $/kg) and Item 2′ (10 $/kg). In the example from Step 2, it all turned out fine. Step 3: Modifying the greedy approximation to give at least 1/2 of the optimal solution Why is this optimal? Well you add the items in the order of what adds the most value. Then it adds Item 3, as this is the item left, which adds the most value per kg. Hence, the algorithm would add Item 2 first, as it gives the most value per kg. Then we would have them ordered, Item 2 (15 $/kg), Item 3 (11.67 $/kg), and Item 1 (10 $/kg). Then it simply adds the items along in that order. But let’s start by understanding what it does.įirst it orders the items based on the highest value per weight. Let’s take a look at the greedy approximation algorithm. To get the optimal solution is difficult, but there exists efficient approximations that are easy to implement. Step 2: A greedy approximation algorithm to solve it efficiently Now this seems easy to solve, or does it? Actually, the Knapsack Problem is NP-complete, which means it is difficult to solve. The Knapsack Problem is to determine the most valuable items to take within some bound of weight.
On the other hand, you could take item 2 and item 3, then you have 4 kg in total and for $50. You cannot take item 3, as that will add up to 6 kg, which is too much. You can take item 1 and item 2, then you have 3 kg and for $45 of value. The challenge is that you can only bring 4 kg. The items – notice the inconsistency of the weight in kg and value in USD$
Finally, item 3 has weight 3 kg, but value $35. The next item, item 2, has weight 1 kg with value $15. In this tutorial we will give an efficient algorithm, the greedy approximation algorithm, which gives at least 1/2 of the optimal solution. Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. The Knapsack Problem is defined as follows.
0 kommentar(er)
