Coders Packet

How to implement Greedy algorithm for Fractional Knapsack problem using Java

By Naman Panpaliya

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.


Greedy Algorithm

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. 



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:

  1. Firstly initialize the weight and value for each knapsack package.
  2. Sort knapsack packages by cost in descending order.
  3. If package select I and if the selected number of package i is enough.
  4. Then stop when browsing all packages.


For the following problem take following data as input:
M=100, n=5
(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

Download Complete Code


No comments yet