Greedy Algorithm
in [Theory]
|
From: jason_box on 11 Apr 2006 03:03 Hello, I was wondering if there is a general proof on proving the optimal solution for making change with the standard Greedy Alogorithm example for change making. I wanted to prove that for any given denomination say C = {8, 4, 2 , 1} for any positive integer n that the greedy algorithm will make change for n using the smallest amount of coins.
From: Jym on 11 Apr 2006 05:21 On Tue, 11 Apr 2006 09:03:15 +0200, jason_box <cppisfun(a)gmail.com> wrote: > Hello, I was wondering if there is a general proof on proving the > optimal solution for making change with the standard Greedy Alogorithm > example for change making. I wanted to prove that for any given > denomination say C = {8, 4, 2 , 1} for any positive integer n that the > greedy algorithm will make change for n using the smallest amount of > coins. If I've understood properly, C is the set of coins you want to use to make change. You know that greedy algorithm for change do not work for any set of coins ? (try making 10 with {7, 5, 1}) -- Hypocoristiquement, Jym.
From: Googmeister on 11 Apr 2006 08:32 jason_box wrote: > Hello, I was wondering if there is a general proof on proving the > optimal solution for making change with the standard Greedy Alogorithm > example for change making. I wanted to prove that for any given > denomination say C = {8, 4, 2 , 1} for any positive integer n that the > greedy algorithm will make change for n using the smallest amount of > coins. Magazine, Nemhauser, and Trotter gave necessary and sufficient conditions for when the greedy coin changing algorithm is optimal. The proof is algorithmic - given a set of denominations, you can efficiently determine whether the greedy algorithm is optimal or not. Here's a reference to a proof. TI : Optimality of a Heuristic Solution for a Class of Knapsack Problems AU : Hu, T. C.; Lenard, M. L. VO : 24 NO : 1 DA : Jan. - Feb., 1976 PP : 193-196 AB : This paper presents a simpler proof for a result of Magazine, Nemhauser, and Trotter, which states recursive necessary and sufficient conditions for the optimality of a heuristic solution for a class of knapsack problems.
From: Mitch on 11 Apr 2006 10:51 Googmeister wrote: > Here's a reference to a proof. > > TI : Optimality of a Heuristic Solution for a Class of Knapsack > Problems > AU : Hu, T. C.; Lenard, M. L. > VO : 24 > NO : 1 > DA : Jan. - Feb., 1976 > PP : 193-196 > AB : This paper presents a simpler proof for a result of Magazine, > Nemhauser, and Trotter, which states recursive necessary and sufficient > conditions for the optimality of a heuristic solution for a class of > knapsack problems. ...where the journal is presumably "Operations Research". Mitch
From: Woeginger Gerhard on 11 Apr 2006 12:21
Googmeister <googmeister(a)gmail.com> wrote: # # jason_box wrote: #> Hello, I was wondering if there is a general proof on proving the #> optimal solution for making change with the standard Greedy Alogorithm #> example for change making. I wanted to prove that for any given #> denomination say C = {8, 4, 2 , 1} for any positive integer n that the #> greedy algorithm will make change for n using the smallest amount of #> coins. # # Magazine, Nemhauser, and Trotter gave necessary and sufficient # conditions for when the greedy coin changing algorithm is optimal. # The proof is algorithmic - given a set of denominations, # you can efficiently determine whether the greedy algorithm is # optimal or not. Yes, Magazine, Nemhauser, and Trotter gave conditions for when the greedy coin changing algorithm is optimal. No, their proof does not help to "efficiently" determine (in polynomial time) whether the greedy algorithm is optimal for a given denomination system. The first efficient algorithm for this problem is due to David Pearson, who derived it in his PhD thesis (Cornell, 1994). This result was published ten years later as David Pearson A polynomial-time algorithm for the change-making problem Operations Research Letters 33, 2005, pages 231-234 The proof is beautiful. --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/ |