Scribd Logo
Upload

Welcome to Scribd!

  • 36 views

    Lecture 16 17

    Uploaded by

    Chhaveesh Agnihotri
    The document summarizes algorithms for solving fractional knapsack problems using greedy approaches. It discusses the greedy algorithm design process and steps for solving fractional knapsack problems. Specifically, it presents an algorithm that picks items in order of highest value per unit weight to fill the knapsack capacity, maximizing the total value. An example demonstrates how this greedy strategy of always selecting the item with the highest value per pound leads to an optimal solution for the fractional knapsack problem.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Lecture 16 17

    Uploaded by

    Chhaveesh Agnihotri
    36 views13 pages
    The document summarizes algorithms for solving fractional knapsack problems using greedy approaches. It discusses the greedy algorithm design process and steps for solving fractional knapsack problems. Specifically, it presents an algorithm that picks items in order of highest value per unit weight to fill the knapsack capacity, maximizing the total value. An example demonstrates how this greedy strategy of always selecting the item with the highest value per pound leads to an optimal solution for the fractional knapsack problem.

    Original Description:

    c

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document summarizes algorithms for solving fractional knapsack problems using greedy approaches. It discusses the greedy algorithm design process and steps for solving fractional knapsack problems. Specifically, it presents an algorithm that picks items in order of highest value per unit weight to fill the knapsack capacity, maximizing the total value. An example demonstrates how this greedy strategy of always selecting the item with the highest value per pound leads to an optimal solution for the fractional knapsack problem.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    36 views13 pages

    Lecture 16 17

    Uploaded by

    Chhaveesh Agnihotri
    The document summarizes algorithms for solving fractional knapsack problems using greedy approaches. It discusses the greedy algorithm design process and steps for solving fractional knapsack problems. Specifically, it presents an algorithm that picks items in order of highest value per unit weight to fill the knapsack capacity, maximizing the total value. An example demonstrates how this greedy strategy of always selecting the item with the highest value per pound leads to an optimal solution for the fractional knapsack problem.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 13

    Apex Institute of Technology

    Department of Computer Science & Engineering


    Bachelor of Engineering (Computer Science & Engineering)
    Design and Analysis of Algorithms– (20CSH-282)
    Prepared By: Mr. Vikas Kumar (E13657)

    04/24/2023 DISCOVER . LEARN . EMPOWER


    1
    Content

    Greedy Method: Understanding of the greedy approach

    Greedy algorithms for Knapsack Fractional Problem

    2
    Greedy Algorithm

    Steps of Greedy Algorithm Design:


    1.Formulate the optimization problem in the form: we
    make a choice and we are left with one sub-problem to
    solve.
    2.

    Show that the greedy choice can lead to an optimal


    solution so that the greedy choice is always safe.

    3. Demonstrate that an optimal solution to original


    problem =   greedy choice + an optimal solution to the
    subproblem

    A good clue is that a greedy strategy will solve the


    problem.
    3
    Greedy Algorithm

    • Many optimization problems can be solved more quickly using a greedy


    approach.
    • The basic principle is that local optimal decisions may be used to build an
    optimal solution.
    • But the greedy approach may not always lead to an optimal solution overall for
    all problems.
    • The key is knowing which problems will work with this approach and which
    will not.

    We will study
    • The activity selection problem
    • Element of a greedy strategy
    • The problem of generating Huffman codes

    4
    Greedy Algorithm
    •Algorithm Greedy(a,n)
    //a[1:n] contains the n inputs.
    {
    Solution :=0;
    For i=1 to n do
    {
    X:=select(a);
    If Feasible(solution, x) then
    Solution :=Union(solution,x);
    }
    Return solution;
    }
    5
    Fractional Knapsack Problem

    6
    Fractional Knapsack Problem

     Knapsack capacity: W
     There are n items: the i-th item has value
    vi and weight wi
     Goal:
     find xi such that for all 0  xi  1, i =
    1, 2, .., n

     wixi  W and

     xivi is maximum

    7
    Fractional Knapsack Problem
    Alg.: Fractional-Knapsack (W, v[n], w[n])
    1. While w > 0 and as long as there are items remaining

    2. pick item with maximum vi/wi

    3. xi  min (1, w/wi)

    4. remove item i from list

    5. w  w – xiwi

     w – the amount of space remaining in the knapsack (w = W)


    8
     Running time: (n) if items already ordered; else (nlgn)
    Fractional Knapsack - Example

     E.g.: 20
    ---
    $80
    Item 3 30 +

    Item 2 50 50
    20 $100
    Item 1 30
    20 +
    10 10 $60

    $60 $100 $120 $240

    $6/pound $5/pound $4/pound

    9
    Fractional Knapsack Problem

     Greedy strategy 1:
     Pick the item with the maximum value
     E.g.:
     W=1
     w1 = 100, v1 = 2
     w2 = 1, v2 = 1
     Taking from the item with the maximum value:
    Total value taken = v1/w1 = 2/100
     Smaller than what the thief can take if choosing the other item
    Total value (choose item 2) = v2/w2 = 1
    10
    Fractional Knapsack Problem

    Greedy strategy 2:
     Pick the item with the maximum value per pound vi/wi
     If the supply of that element is exhausted and the thief can
    carry more: take as much as possible from the item with
    the next greatest value per pound
     It is good to order items based on their value per pound

    11
    REFERENCES
    Text books:
    • Cormen, Leiserson, Rivest, Stein, “Introduction to Algorithms”, Prentice Hall of India, 3rd edition 2012.
    problem, Graph coloring.

    Websites:
    • https://www.tutorialspoint.com/data_structures_algorithms/kruskals_spanning_tree_algorithm.htm
    • https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
    THANK YOU

    You might also like