• Bhupendra Singh Mandloi
• Vivek Rai

The Knapsack problem is a one type of combinatorial problem. The purpose of combinatorial problem is to find better object (optimal objects) from the given set of objects, it is also known as combinatorial optimization. In combinatorial algorithm always try for choose better objects, like Travelling sales man problem, minimum spanning tree problem, Knapsack problem. Objective of knapsack problem is to produce maximum profit without exceed knapsack capacity. Purpose of this paper is that without feasible solution, find direct optimal solution. For direct optimal solution first we have to calculate per unit profit, and then we have to keep per unit profit values into linear array according to the descending order, now pick the values from array and putdown into knapsack until knapsack full or until array empty. Due to this we don’t required to generate multiple feasible solutions, so proposed method will provide faster solution in comparisons. Solution of knapsack problem by the proposed method reduces time and space complexity. Now the knapsack problem can be solved by linear time complexity and it will be comes under polynomial type or P type problems.

Greedy Method, Knapsack, feasible solution, optimal solution.

"A Study of Efficient Greedy Approach for Knapsack Problem", International Journal of Emerging Technologies and Innovative Research (www.jetir.org), ISSN:2349-5162, Vol.6, Issue 3, page no.273-278, March-2019, Available :http://www.jetir.org/papers/JETIRAI06057.pdf

"A Study of Efficient Greedy Approach for Knapsack Problem", International Journal of Emerging Technologies and Innovative Research (www.jetir.org | UGC and issn Approved), ISSN:2349-5162, Vol.6, Issue 3, page no. pp273-278, March-2019, Available at : http://www.jetir.org/papers/JETIRAI06057.pdf