Posts

Image
         The knapsack problem is a classic optimization problem in computer science, mathematics, and operations research. It is a problem of combinatorial optimization, where the goal is to optimize a function subject to a set of constraints.  The problem is framed in terms of a knapsack, which is a container with a limited capacity. A set of items is given, each with a weight and a value. The objective is to select a subset of items that maximizes the value, subject to the constraint that the sum of the weights of the selected items does not exceed the capacity of the knapsack.   Fig 1: Knapsack Problem The problem can be formulated mathematically as follows:     Maximize ∑ vi xi     Subject to ∑ wi xi ≤ W     xi ∈ {0, 1}             where vi is the value of the i-th item, wi is its weight, W is the capacity of the knapsack, and xi is a bin...
5 comments
Read more

APPLICATION OF PRIM' s AND KRUSKAL' s ALGORITHM IN REAL-LIFE SCENARIOUS

Image
  Welcome! Let’s start with some informal context. Let me ask you something:             Have you ever used Google Maps for directions? Have you ever used Social Media apps like Facebook or Instagram? Well, guess what, you have been using graphs all along. Let’s see what these algorithms actually are and how they work! If “Yes” to any of these questions, then you’ve definitely used graphs and you didn’t even know it! Surprised? I was, too!              Through this blog, we will go through two essential, yet fun algorithms and compare them in real-world scenarios. Let’s say our task is to find minimum path from current location to destination in such a way that we need to find out all the paths and from this we need to find minimum path and the minimum cost of path. Now how do we find that out? We can use  Prim’s Algorithm or Kruskal’s Algorithm . v    Both Prims and Krus...
Post a Comment
Read more