This blog will help you to know about the greedy algorithm and how to implement it for fractional knapsack problems using Java.
In this blog, you will learn about the Greedy algorithm and its application and how to implement the Greedy algorithm for the fractional knapsack problem.
A greedy algorithm is used for solving optimization problems it is a simple, intuitive algorithm. These are like dynamic program algorithms. The Greedy Algorithm makes the optimal choice at each step and solves the problem in an optimal way.
APPLICATIONS OF GREEDY ALGORITHM
There are many applications of the Greedy algorithm but Dijkstra's algorithm, Huffman encoding, and Job sequencing provide the optimal solutions. Some of its applications are explained below
Dijkstra's Algorithm: Dijkstra's algorithm is very much similar to Prim's algorithm and is used to find the shortest path between nodes in a graph.
Huffman Coding: This is another example where the greedy approach is successful. The Huffman algorithm analyzes a message and depending on the frequencies of the characters used in the message, it assigns a variable-length encoding for each symbol.
Explanation of code:
For the following problem take following data as input:
(w1, w2, w3, w4, w5) = (10, 30, 40, 25, 20)
(p1, p2, p3, p4, p5) = (20, 50, 10, 60, 80)
Here is the Output for the following Greedy algorithm for the Fractional Knapsack problem
Submitted by Naman Panpaliya (Naman9999)
Download packets of source code on Coders Packet