📄 page447.html
字号:
<HTML><HEAD><TITLE>Example-0/1 Knapsack Problem Again</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="tex2html6317" HREF="page448.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6315" HREF="page439.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6311" HREF="page446.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6319" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0014250000000000000000">Example-0/1 Knapsack Problem Again</A></H2><P>Consider again the 0/1 knapsack problem described in Section <A HREF="page438.html#secalgsknapsack"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.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.The solution to the problem has the form <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67845" SRC="img1742.gif" >,where <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67687" SRC="img1713.gif" > is one if the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > item is placed in the knapsackand zero otherwise.Each item has both a <em>weight</em>, <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67677" SRC="img1712.gif" >,and a <em>profit</em>, <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline57875" SRC="img85.gif" >.The goal is to maximize the total profit,<P> <IMG WIDTH=278 HEIGHT=44 ALIGN=BOTTOM ALT="displaymath67839" SRC="img1743.gif" ><P>subject to the knapsack capacity constraint<P> <IMG WIDTH=295 HEIGHT=44 ALIGN=BOTTOM ALT="displaymath67672" SRC="img1717.gif" ><P><P>A partial solution to the problem is one in which only the first<I>k</I> items have been considered.That is, the solution has the form <IMG WIDTH=145 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67857" SRC="img1744.gif" >,where <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67859" SRC="img1745.gif" >.The partial solution <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67861" SRC="img1746.gif" > is feasible if and only if<P><A NAME="eqnalgsbandbi"> </A> <IMG WIDTH=500 HEIGHT=47 ALIGN=BOTTOM ALT="equation32636" SRC="img1747.gif" ><P>Clearly if <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67861" SRC="img1746.gif" > is infeasible,then every possible complete solution containing <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67861" SRC="img1746.gif" > is also infeasible.<P>If <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67861" SRC="img1746.gif" > is feasible,the total profit of any solution containing <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67861" SRC="img1746.gif" > is bounded by<P><A NAME="eqnalgsbandbii"> </A> <IMG WIDTH=500 HEIGHT=49 ALIGN=BOTTOM ALT="equation32641" SRC="img1748.gif" ><P>That is, the bound is equal the <em>actual</em> profit accrued from the <I>k</I> itemsalready considered plusthe sum of the profits of the remaining items.<P>Clearly, the 0/1 knapsack problem can be solved using a backtracking algorithm.Furthermore, by using Equations <A HREF="page447.html#eqnalgsbandbi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and <A HREF="page447.html#eqnalgsbandbii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>a branch-and-bound solver can potentially prune the solution space,thereby arriving at the solution more quickly.<P>For example, consider the 0/1 knapsack problem with <I>n</I>=6 itemsgiven in Table <A HREF="page438.html#tblalgsknapsack"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.There are <IMG WIDTH=53 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline67875" SRC="img1749.gif" > possible solutions andthe solution space contains <IMG WIDTH=104 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline67877" SRC="img1750.gif" > nodes.The simple <tt>DepthFirstSolver</tt> given in Program <A HREF="page443.html#progdepthFirstSolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>visits all 127 nodes and generates all 64 solutionsbecause it does a complete traversal of the solution tree.The <tt>BreadthFirstSolver</tt> of Program <A HREF="page444.html#progbreadthFirstSolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> behaves similarly.On the other hand, the <tt>DepthFirstBranchAndBoundSolver</tt>shown in Program <A HREF="page446.html#progdepthFirstBranchAndBoundSolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> visits only 67 nodesand generates only 27 complete solutions.In this case,the branch-and-bound technique prunes almost half the nodesfrom the solution space!<P><HR><A NAME="tex2html6317" HREF="page448.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6315" HREF="page439.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6311" HREF="page446.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6319" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -