top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

What does mean of Knapsack problem in optimization?

+1 vote
What does mean of Knapsack problem in optimization?
posted Dec 30, 2014 by Amit Kumar Pandey

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

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

answer Dec 30, 2014 by Prakash
Similar Questions
+1 vote

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.

+2 votes

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.

+2 votes

I have very high and limited knowledge of compiler's functionality.
As per my knowledge, Compiler does it's job using following steps:
1. Lexical analysis
2. Syntactic analysis
3. Semantic analysis
4. Pre-optimization of internal representation.
5. Code generation
6. Post optimization.

Can some one please explain about 4, 5 and 6 steps ? What they signify ?