📄 page454.html
字号:
<HTML>
<HEAD>
<TITLE>Example-0/1 Knapsack Problem Again</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="tex2html7527" HREF="page455.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page455.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="tex2html7525" HREF="page446.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page446.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="tex2html7521" HREF="page453.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page453.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="tex2html7529" 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="tex2html7530" 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>
<H2><A NAME="SECTION0015250000000000000000">Example-0/1 Knapsack Problem Again</A></H2>
<P>
Consider again the 0/1 knapsack problem described in Section <A HREF="page445.html#secalgsknapsack" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page445.html#secalgsknapsack"><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>.
We are given a set of <I>n</I> items
from 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=108 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68635" SRC="img1851.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1851.gif" >,
where <IMG WIDTH=12 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline68477" SRC="img1819.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1819.gif" > is one if the <IMG WIDTH=17 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58387" SRC="img77.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img77.gif" > item is placed in the knapsack
and zero otherwise.
Each item has both a <em>weight</em>, <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" >,
and a <em>profit</em>, <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" >.
The goal is to maximize the total profit,
<P> <IMG WIDTH=277 HEIGHT=43 ALIGN=BOTTOM ALT="displaymath68629" SRC="img1852.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1852.gif" ><P>
subject to the knapsack capacity constraint
<P> <IMG WIDTH=296 HEIGHT=43 ALIGN=BOTTOM ALT="displaymath68462" SRC="img1823.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1823.gif" ><P>
<P>
A partial solution to the problem is one in which only the first
<I>k</I> items have been considered.
I.e., the solution has the form <IMG WIDTH=147 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68647" SRC="img1853.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1853.gif" >,
where <IMG WIDTH=67 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline68649" SRC="img1854.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1854.gif" >.
The partial solution <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68651" SRC="img1855.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1855.gif" > is feasible if and only if
<P><A NAME="eqnalgsbandbi"> </A> <IMG WIDTH=500 HEIGHT=47 ALIGN=BOTTOM ALT="equation32825" SRC="img1856.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1856.gif" ><P>
Clearly if <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68651" SRC="img1855.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1855.gif" > is infeasible,
then every possible complete solution containing <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68651" SRC="img1855.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1855.gif" > is also infeasible.
<P>
If <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68651" SRC="img1855.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1855.gif" > is feasible,
the total profit of any solution containing <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68651" SRC="img1855.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1855.gif" > is bounded by
<P><A NAME="eqnalgsbandbii"> </A> <IMG WIDTH=500 HEIGHT=49 ALIGN=BOTTOM ALT="equation32830" SRC="img1857.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1857.gif" ><P>
I.e., the bound is equal the <em>actual</em> profit accrued from the <I>k</I> items
already considered plus
the 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="page454.html#eqnalgsbandbi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page454.html#eqnalgsbandbi"><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="page454.html#eqnalgsbandbii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page454.html#eqnalgsbandbii"><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>
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 items
given in Table <A HREF="page445.html#tblalgsknapsack" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page445.html#tblalgsknapsack"><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>.
There are <IMG WIDTH=53 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline68665" SRC="img1858.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1858.gif" > possible solutions and
the solution space contains <IMG WIDTH=105 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68667" SRC="img1859.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1859.gif" > nodes.
The simple <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>
visits all 127 nodes and generates all 64 solutions
because it does a complete traversal of the solution tree.
The <tt>BreadthFirstSolver</tt> of 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> behaves similarly.
On the other hand, the <tt>DepthFirstBranchAndBoundSolver</tt>
shown in Program <A HREF="page453.html#progsolution4c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page453.html#progsolution4c"><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> visits only 67 nodes
and generates only 27 complete solutions.
In this case,
the branch-and-bound technique prunes almost half the nodes
from the solution space!
<P>
<HR><A NAME="tex2html7527" HREF="page455.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page455.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="tex2html7525" HREF="page446.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page446.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="tex2html7521" HREF="page453.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page453.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="tex2html7529" 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="tex2html7530" 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> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -