A Study of Analyzing Greedy Approach for Fractional Knapsack Problem

Abstract: The Knapsack Problem belongs to a large class of problems known as Combinatorial Optimization Problem. This problem is to maximize the obtained profit without exceeding the knapsack capacity. It is a very special case of the well-known Integer Linear Programming Problem. The purpose of this paper is to analyze several feasible solutions to a Fractional Knapsack Problem using greedy approach. Based on the knapsack algorithm to take different feasible solutions, in this set of feasible solutions, particular solution that satisfies the objective of the function. Such solution is called optimum solution. The optimum selection is without revising previously generated solutions. The greedy choices are made one after the other, reducing each given problem instance to smaller one. The greedy choices bring efficiency in solving the problem with the help of sub problems.

Keywords: Knapsack, Greedy Programming, Feasible Solutions.