discuss the greedy algorithm for knapsack problem in detail
Answers
Answer:
Greedy algorithms are like dynamic programming algorithms that are often used to solve optimal problems (find best solutions of the problem according to a particular criterion).
Greedy algorithms implement optimal local selections in the hope that those selections will lead to an optimal global solution for the problem to be solved. Greedy algorithms are often not too hard to set up, fast (time complexity is often a linear function or very much a second-order function). Besides, these programs are not hard to debug and use less memory. But the results are not always an optimal solution.
Greedy strategies are often used to solve the combinatorial optimization problem by building an option A. Option A is constructed by selecting each component Ai of A until complete (enough n components). For each Ai, you choose Ai optimally. In this way, it is possible that at the last step you have nothing to select but to accept the last remaining value.
There are two critical components of greedy decisions:
Way of greedy selection. You can select which solution is best at present and then solve the subproblem arising from making the last selection. The selection of greedy algorithms may depend on previous selections. But it cannot depend on any future selection or depending on the solutions of subproblems. The algorithm evolves in a way that makes selections in a loop, at the same time shrinking the given problem to smaller subproblems.
Optimal substructure. You perform the optimal substructure for a problem if the optimal solution of this problem contains optimal solutions to its subproblems.
A greedy algorithm has five components:
A set of candidates, from which to create solutions.
A selection function, to select the best candidate to add to the solution.
A feasible function is used to decide if a candidate can be used to build a solution.
An objective function, fixing the value of a solution or an incomplete solution.
An evaluation function, indicating when you find a complete solution.
Explanation:
i hope it will help you and
please mark me as brainlist answer