# What does mean of Knapsack problem in optimization?

+1 vote
259 views
What does mean of Knapsack problem in optimization?
posted Dec 30, 2014

+1 vote

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
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.

Similar Questions
+1 vote

``````  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.

Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way that they sum up to S.