Thread: greedy algorithm problem

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    1

    greedy algorithm problem

    I really need help to solve a problem using greedy algorithm, I try to search in the net for a code in c, but I find nothing. The kind of problem that I need to solve is fractional or knapsack problem or problem escalation intervals or tree problem Huffman but I need to solve using the greedy algorithm. (Keywords: greedy algorithms, greedy algorithm).
    Thank's.

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Remember that in general greedy algorithms have this structurte
    Code:
    Greedy (E : set of elements)
    1. F = Ø
    2. while E = Ø 6 do
    3.     Greedy choice x ∈ E
    4.     E = E − {x}
    5.     if F ∪ {x} feasible then
    6.           F = F ∪ {x}
    7.     end if
    8. end while
    9. return F
    Hope this helps
    Last edited by std10093; 10-06-2012 at 07:36 AM. Reason: style of code

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Here also pseudocode for discrete problem of knapsack
    Code:
    Discrete-Knapsack (X : set of objects , a, c : respective weights and
    values, b : weight of knapsack)
     Descending-Sort(ci/ai)
     S = Ø
     for i = 1 to n
         if b ≥ ai
            S = S ∪ {xi}
            b = b − ai
        end if
     end for

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Greedy XGrabKeyboard
    By belnac in forum Linux Programming
    Replies: 3
    Last Post: 05-18-2010, 01:00 PM
  2. what is the algorithm in this problem..
    By cfan in forum C Programming
    Replies: 2
    Last Post: 08-04-2009, 11:52 AM
  3. iterated greedy!!
    By joan in forum C++ Programming
    Replies: 71
    Last Post: 12-11-2006, 03:27 PM
  4. ITERATED GREEDY ALGORITHM. Help!!
    By joan in forum C++ Programming
    Replies: 0
    Last Post: 12-05-2006, 12:45 PM
  5. Is Kazaa being greedy?
    By minesweeper in forum A Brief History of Cprogramming.com
    Replies: 29
    Last Post: 11-05-2002, 04:39 PM

Tags for this Thread