page481.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 158 行 · 第 1/2 页
HTML
158 行
<HTML>
<HEAD>
<TITLE>Exercises</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html7856" HREF="page482.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page482.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7854" HREF="page440.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page440.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html7848" HREF="page480.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page480.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7858" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7859" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H1><A NAME="SECTION0015600000000000000000">Exercises</A></H1>
<P>
<OL><LI>
Consider the greedy strategy for counting out change
given in Section <A HREF="page442.html#secalgschange" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page442.html#secalgschange"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
Let <IMG WIDTH=105 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68427" SRC="img1810.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1810.gif" > be the set of available denominations.
E.g., the set <IMG WIDTH=144 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69599" SRC="img2065.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2065.gif" > represents the denominations
of the commonly circulated Canadian coins.
What condition(s) must the set of denominations satisfy
to ensure the greedy algorithm always finds an optimal solution?<LI>
Devise a greedy algorithm to solve optimally
the scales balancing problem described in Section <A HREF="page447.html#secalgsscales" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page447.html#secalgsscales"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<OL><LI>
Does your algorithm always find the optimal solution?<LI>
What is the running time of your algorithm?
</OL><LI>
Consider the following 0/1-knapsack problem:
<DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=3 BORDER FRAME=HSIDES RULES=GROUPS>
<COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
<I>i</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=14 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline68467" SRC="img1818.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1818.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58415" SRC="img85.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img85.gif" > </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6 </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 8 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 9 </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP COLSPAN=3><I>C</I>=18</TD></TR>
</TBODY>
</TABLE>
</P></DIV>
<OL><LI>
Solve the problem using the greedy by profit,
greedy by weight and greedy by profit density strategies.<LI>
What is the optimal solution?
</OL><LI> <A NAME="exercisealgsbfsi"> </A>
Consider the breadth-first solver shown in Program <A HREF="page451.html#progsolution3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page451.html#progsolution3c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
Suppose we replace the queue (line 3)
with a <em>priority queue</em>.
<OL><LI>
How should the solutions in the priority queue be prioritized?<LI>
What possible benefit might there be from using
a priority queue rather than a FIFO queue?
</OL><LI> <A NAME="exercisealgsbfsii"> </A>
Repeat Exercise <A HREF="page481.html#exercisealgsbfsi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page481.html#exercisealgsbfsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>,
but this time consider what happens if
we replace the queue with a <em>LIFO stack</em>.<LI>
Repeat Exercises <A HREF="page481.html#exercisealgsbfsi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page481.html#exercisealgsbfsi"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> and <A HREF="page481.html#exercisealgsbfsii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page481.html#exercisealgsbfsii"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>,
but this time consider a
<em>branch-and-bound</em> breadth-first solver.<LI> <A NAME="exercisealgsgraph"> </A>
(This question should be attempted
<em>after</em> reading Chapter <A HREF="page523.html#chapgraphs" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page523.html#chapgraphs"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>).
For some problems the solution space
is more naturally a graph rather than a tree.
<OL><LI>
What problem arises if we use the <tt>DepthFirstSolver</tt>
given in Program <A HREF="page450.html#progsolution2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page450.html#progsolution2c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> to explore
a search space that is not a tree.<LI>
Modify the <tt>DepthFirstSolver</tt> so that it
explores a solution space that is not a tree.
<b>Hint</b>: See Program <A HREF="page552.html#proggraph1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page552.html#proggraph1c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.<LI>
What problem arises if we use the <tt>BreadthFirstSolver</tt>
given in Program <A HREF="page451.html#progsolution3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page451.html#progsolution3c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> to explore
a search space that is not a tree.<LI>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?