page438.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 120 行
HTML
120 行
<HTML><HEAD><TITLE>Example-0/1 Knapsack Problem</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="tex2html6216" HREF="page439.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6214" HREF="page434.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6210" HREF="page437.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6218" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0014120000000000000000">Example-0/1 Knapsack Problem</A></H2><A NAME="secalgsknapsack"> </A>The <em>0/1 knapsack problem</em><A NAME=32145> </A>is closely related to the change counting problem discussed in thepreceding section:We are given a set of <I>n</I> itemsfrom which we are to select some number of items to be carried in a knapsack.Each item has both a <em>weight</em> and a <em>profit</em>.The objective is to chose the set of items that fits in the knapsackand maximizes the profit.<P>Let <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67677" SRC="img1712.gif" > be the weight of the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > item, <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57875" SRC="img85.gif" > be the profit accrued when the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > itemis carried in the knapsack, and<I>C</I> be the capacity of the knapsack.Let <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67687" SRC="img1713.gif" > be a variable the value of which is either zero or one.The variable <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67687" SRC="img1713.gif" > has the value onewhen the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > item is carried in the knapsack.<P>Given <IMG WIDTH=114 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67693" SRC="img1714.gif" > and <IMG WIDTH=104 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67695" SRC="img1715.gif" >,our <em>objective</em> is to maximize<P> <IMG WIDTH=275 HEIGHT=44 ALIGN=BOTTOM ALT="displaymath67671" SRC="img1716.gif" ><P>subject to the constraint<P> <IMG WIDTH=295 HEIGHT=44 ALIGN=BOTTOM ALT="displaymath67672" SRC="img1717.gif" ><P><P>Clearly, we can solve this problem by exhaustively enumeratingthe feasible solutions and selecting the one with the highest profit.However, since there are <IMG WIDTH=15 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline60291" SRC="img558.gif" > possible solutions,the running time required for the brute-force solutionbecomes prohibitive as <I>n</I> gets large.<P>An alternative is to use a greedy solution strategy whichsolves the problem by putting items into the knapsack one-by-one.This approach is greedy because once an item has been put into the knapsack,it is never removed.<P>How do we select the next item to be put into the knapsack?There are several possibilities:<DL ><DT><STRONG>Greedy by Profit</STRONG><DD> At each step select from the remaining items the one with the highest profit (provided the capacity of the knapsack is not exceeded). This approach tries to maximize the profit by choosing the most profitable items first. <DT><STRONG>Greedy by Weight</STRONG><DD> At each step select from the remaining items the one with the least weight (provided the capacity of the knapsack is not exceeded). This approach tries to maximize the profit by putting as many items into the knapsack as possible. <DT><STRONG>Greedy by Profit Density</STRONG><DD> At each step select from the remaining items the one with the largest <em>profit density</em>, <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67701" SRC="img1718.gif" > (provided the capacity of the knapsack is not exceeded). This approach tries to maximize the profit by choosing items with the largest profit per unit of weight.<P> </DL>While all three approaches generate feasible solutions,we cannot guarantee that any of them will always generate the optimal solution.In fact, it is even possible that none of them does!Table <A HREF="page438.html#tblalgsknapsack"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives an example where this is the case.<P><P><A NAME="32161"> </A><P> <A NAME="tblalgsknapsack"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=8 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=3> greedy by</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><P> <I>i</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67677" SRC="img1712.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57875" SRC="img85.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=38 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67701" SRC="img1718.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> profit </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> weight </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> density </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> optimal solution </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 100 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 40 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0.4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 50 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 35 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0.7 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 45 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 18 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0.4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 20 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0.2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1.0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0.4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 0 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP COLSPAN=4>total weight</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 100 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 80 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 85 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 100 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP COLSPAN=4> total profit</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 40 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 34 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 51 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 55 </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> 0/1 knapsack problem example (<I>C</I>=100).</CAPTION></TABLE></P></DIV><P><P>The bottom line about greedy algorithms is this:Before using a greedy algorithmyou must make sure that it always gives the correct answer.Fortunately, in many cases this is true.<P><HR><A NAME="tex2html6216" HREF="page439.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6214" HREF="page434.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6210" HREF="page437.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6218" 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 © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?