![]() ![]() Genetic Algorithms help generate high-quality solutions to optimization problems, like Knapsack, but do not guarantee an optimal solution. While solving a problem with a Genetic Algorithm, we need to model it to undergo evolution through natural operations like Mutation, Crossover, Reproduction, and Selection. As per Darwin’s Theory of Evolution, the fittest individuals in an environment survive and pass their traits on to the future generations while the weak characteristics die long the journey. ![]() Genetic Algorithms is a class of algorithms inspired by the process of natural selection. Genetic Algorithm inspired by the Theory of Evolution does exactly this for us. This raises a need for a polynomial-time solution to the Knapsack problem that need not generate an optimal solution instead, a good quick, high-quality approximation is also okay. The numeric value of the input W is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length. This makes the complexity of above solution O(n.2^m). Given that the computation needs to happen by a factor of W, the maximum times the function will execute will be proportional to the max value of W which will be 2^m where m is the number of bits required to represent the weight W. Although it looks like a polynomial-time solution, it is indeed a pseudo-polynomial time solution. The above solution runs with a complexity of O(n.W) where n is the total number of items and W is the maximum weight the knapsack can carry. ![]() memo = def knapsack (W, w, v, n): if n = 0 or W = 0 : return 0 # if weight of the nth item is more than the weight # available in the knapsack the skip it if (w > W): return knapsack(W, w, v, n - 1 ) # Check if we already have an answer to the sunproblem if (W, n) in memo: return memo # find value of the knapsack when the nth item is picked value_picked = v + knapsack(W - w, w, v, n - 1 ) # find value of the knapsack when the nth item is not picked value_notpicked = knapsack(W, w, v, n - 1 ) # return the maxmimum of both the cases # when nth item is picked and not picked value_max = max (value_picked, value_notpicked) # store the optimal answer of the subproblem memo = value_max return value_max Run-time Complexity We remember the optimal solution of the subproblem in a hash table, and we reuse the solution instead of recomputing. The algorithm covers all possible cases by considering every item picked and not picked. The solution to the Knapsack problem uses Recursion with memoization to find the optimal solution. ![]() Formally, the problem statement states that, given a set of items, each with a weight and a value, determine the items we pack in the knapsack with a constrained maximum weight that the knapsack can hold, such the the total value of the knapsack is maximum. The Knapsack problem is an optimization problem that deals with filling up a knapsack with a bunch of items such that the value of the Knapsack is maximized. In this essay, we look at an approximation algorithm inspired by genetics that finds a high-quality solution to it in polynomial time. The 0/1 Knapsack Problem has a pseudo-polynomial run-time complexity. The problem has been studied since 1897, and it refers to optimally packing the bag with valuable items constrained on the max weight the bag can carry. The Knapsack problem is one of the most famous problems in computer science. ![]()
0 Comments
Leave a Reply. |