page437.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 53 行

HTML
53 行
字号 
<HTML><HEAD><TITLE>Greedy Algorithm</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html6207" HREF="page438.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6205" HREF="page435.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6201" HREF="page436.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html6209" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0014112000000000000000">Greedy Algorithm</A></H3><P>A cashier does not really consider all the possibleways in which to count out a given sum of money.Instead, he counts out the required amountbeginning with the largest denominationand proceeding to the smallest denomination.<P>For example,suppose we have ten coins:five pennies, two nickels, two dimes, and one quarter.That is,  <IMG WIDTH=314 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67665" SRC="img1710.gif"  >.To count out 32 cents,we start with a quarter,then add a nickel followed by two pennies.This is a greedy strategy because once a coin has been counted out,it is never taken back.Furthermore, the solution obtained is the correct solutionbecause it uses the fewest number of coins.<P>If we assume that the pieces of money (notes and coins)are sorted by their denomination,the running time for the greedy algorithm is <I>O</I>(<I>n</I>).This is significantly better than that of the brute-forcealgorithm given above.<P>Does this greedy algorithm always produce the correct answer?Unfortunately it does not.Consider what happens if we introduce a 15-cent coin.Suppose we are asked to count out 20 centsfrom the following set of coins:  <IMG WIDTH=153 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67669" SRC="img1711.gif"  >.The greedy algorithm selects 15 followed by five ones--six coins in total.Of course, the correct solution requires only two coins.The solution found by the greedy strategy is a feasible solution,but it does not minimize the objective function.<P><HR><A NAME="tex2html6207" HREF="page438.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6205" HREF="page435.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6201" HREF="page436.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html6209" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page437.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page437.html 源码文件，采用 HTML 编程语言编写，共 53 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?