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. # store the optimal answer of the subproblem Value_max = max(value_picked, value_notpicked) Value_notpicked = knapsack(W, w, v, n - 1) # find value of the knapsack when the nth item is not picked Value_picked = v + knapsack(W - w, w, v, n - 1) # find value of the knapsack when the nth item is picked # Check if we already have an answer to the sunproblem # if weight of the nth item is more than the weight 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 kommentar(er)
