This is post is basically for solving the Knapsack problem, very famous problem in optimization community, using dynamic programming. But remember this problem can be solved using various approaches with different complexities, but here I shall talk about only dynamic programming, specifically bottom-up approach. So lets first talk about what is Knapsack problem for the people who are unfamiliar with it. The Knapsack problem states that “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”. Lets consider a concrete example , suppose you have a Knapsack and you have lots of books and articles. You are planning to go somewhere in your vacation and you want to keep some important books and articles with you. The Knapsack has fix capacity so you cannot keep all the books and articles that you got inside the knapsack.
تعليقات: 0
إرسال تعليق