This is one of the optimization algorithm where we try lot of options and optimize (maximize or minimize based on the requirement) the output. For this algorithm, we will be given list of items, their size/weight and their values. We have a knapsack (bag pack) with a limited size/weight and we need to find the best choice of items to fit those in the knapsack so that we can maximize the value.
One of the examples where we can use this algorithm is while preparing for travelling (back packing for trekking or etc). We wish we can take everything but we will have limited backpack and need to choose the best items. One other classic example is a thief trying to rob a house or a shop. He can carry limited items and he needs to take the best choice so that he can maximize the value. (If he is a programmer, I am sure he will use this algorithm ;))
Here we will discuss only the classic flavor of knapsack problem, which is called 0-1 knapsack. It means, we can either take the full item or not. We can’t take the part of the item available.
Read full article from Algorithm – Knapsack | Sada Kurapati
No comments:
Post a Comment