What does mean of Knapsack problem in optimization?

Question

Please help me to solve the Knapsack problem using greedy algorithms.

  Profit Weight    
1) 30    10
2) 50    5
3) 20    12
4) 70    40
5) 90    15

The knapsack size is 50. Make the selection criteria based on : min weight, max profit and Ratio.

Answer 1

Knapsack problem is one of the many combinatorial optimization problems. The wikipedia definition of knapsack problem is:
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible

So the aim is to find a solution i.e proper combination of items (I1, I2, I3.......In) so that sum of masses is less than or equal to maximum limit and total value is as large as possible.

There are many variants of this problem.
1) 0-1 knapsack
2) fractional knapsack
3) quadritic knapsack
and so on.

The knapsack problem is known to np-hard. Since it is combinatorial optimization problem, it's solution approach starts from the recursive to bractracking, to DP and finally greed. Dynamic programming approach is used in case of 0-1 knapsack problem as well as fractional knapsack problem since these problems have overlapping subproblem as well as these problems contain optimal substructure. Fractional knapsack problem is special case of 0-1 knapsack and it follows the matroid theory which is essential for it to be solvable using greedy algorithm design technique.
Thus using DP the problem can be solved effeciently but still the order of solution is exponential. The fractional knapsack being a special case is solvable in polynomial time using greedy approach.