Greedy Algorithm - Knapsack Problem

Greedy Algorithm - Knapsack Problem

• 1.
  Knapsack problem M.Madhu Bala Mphil(CS)
• 2.
  OPTIMIZATION PROBLEM (Cont.) An optimization problem:  Given a problem instance, a set of constraints and an objective function.  Find a feasible solution for the given instance.  either maximum or minimum depending on the problem being solved.  constraints specify the limitations on the required solutions.
• 3.
  SOLUTION FOR OPTIMIZATIONPROBLEM For some optimization problems, • Dynamic Programming is “overkill” • Greedy Strategy is simpler and more efficient .
• 4.
  DYNAMIC PROGRAMMING VSGREEDY Dynamic Programming Greedy Algorithm At each step, the choice is determined based on solutions of sub problems. At each step, we quickly make a choice that currently looks best. A local optimal (greedy) choice Sub-problems are solved first. Greedy choice can be made first before solving further sub- problems. Bottom-up approach Top-down approach Can be slower, more complex Usually faster, simpler
• 5.
   Characteristics ofgreedy algorithm:  make a sequence of choices  each choice is the one that seems best so far, only depends on what's been done so far  choice produces a smaller problem to be solved GREEDY METHOD
• 6.
  PHASES OF GREEDYALGORITHM  A greedy algorithm works in phases.  At each phase:  takes the best solution right now, without regard for future consequences  choosing a local optimum at each step, and end up at a global optimum solution.
• 7.
  KNAPSACK PROBLEM There aretwo version of knapsack problem 1. 0-1 knapsack problem:  Items are indivisible. (either take an item or not)  can be solved with dynamic programming. 2. Fractional knapsack problem:  Items are divisible. (can take any fraction of an item)  It can be solved in greedy method
• 8.
  0-1 KNAPSACK PROBLEM: A thief robbing a store finds n items.  ith item: worth vi value of item and wi weight of item  W, wi, vi are integers.  He can carry at most W pounds.
• 9.
  FRACTIONAL KNAPSACK PROBLEM: A thief robbing a store finds n items.  ith item: worth vi value of item and wi weight of item  W, wi, vi are integers.  He can carry at most W pounds.  He can take fractions of items.
• 10.
  THE OPTIMAL KNAPSACKALGORITHM  Input:  an integer n  positive values wi and vi such that 1  i  n  positive value W.  Output:  n values of xi such that 0  xi  1  Total profit
• 11.
  Initialization:  Sort then objects from large to small based on their ratios vi / wi .  We assume the arrays w[1..n] and v[1..n] store the respective weights and values after sorting.  initialize array x[1..n] to zeros.  weight = 0; i = 1; THE OPTIMAL KNAPSACK ALGORITHM
• 12.
  while (i n and weight < W) do if weight + w[i]  W then x[i] = 1 else x[i] = (W – weight) / w[i] weight = weight + x[i] * w[i] i++ THE OPTIMAL KNAPSACK ALGORITHM
• 13.
  KNAPSACK - EXAMPLE Problem: n= 3 W= 20 (v1, v2, v3) = (25, 24, 15) (w1, w2, w3) = (18, 15, 10)
• 14.
  Solution:  Optimal solution: x1 = 0  x2 = 1  x3 = 1/2  Total profit = 24 + 7.5 = 31.5 KNAPSACK - EXAMPLE
• 15.
  THANK YOU