📄 上大_net-0-1背包问题(回朔法).htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0057)http://www.shangda.net/printpage.asp?BoardID=110&ID=48550 -->
<!--HTTP头--><HTML><HEAD><TITLE>上大.net-0/1背包问题(回朔法)</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 5.50.4134.100" name=GENERATOR>
<META
content="上大.net,shangda.net,shangda,上海大学,上海大学BBS,上海大学论坛,上大,上大BBS,上大论坛,ShangHai University,学生论坛,上大考研,上海大学考研,上大招聘,上海大学招聘,上海大学社团"
name=keywords>
<META content=上海大学综合性学生论坛 name=description><!--默认风格-->
<STYLE type=text/css>A:link {
COLOR: #000000; TEXT-DECORATION: none
}
A:active {
COLOR: #000000; TEXT-DECORATION: none
}
A:visited {
COLOR: #000000; TEXT-DECORATION: none
}
A:hover {
COLOR: #4455aa; TEXT-DECORATION: underline
}
BODY {
SCROLLBAR-FACE-COLOR: #dee3e7; FONT-SIZE: 12px; SCROLLBAR-HIGHLIGHT-COLOR: #ffffff; SCROLLBAR-SHADOW-COLOR: #dee3e7; COLOR: #000000; SCROLLBAR-3DLIGHT-COLOR: #d1d7dc; SCROLLBAR-ARROW-COLOR: #006699; SCROLLBAR-TRACK-COLOR: #efefef; FONT-FAMILY: 宋体; SCROLLBAR-DARKSHADOW-COLOR: #98aab1
}
FONT {
LINE-HEIGHT: normal
}
TD {
FONT-SIZE: 12px; LINE-HEIGHT: 15px; FONT-FAMILY: 宋体
}
TH {
FONT-WEIGHT: bold; FONT-SIZE: 12px; BACKGROUND-IMAGE: url(Skins/Default/css/default/bg1.gif); COLOR: white; BACKGROUND-COLOR: #4455aa
}
TD.TableTitle2 {
BACKGROUND-COLOR: #e4e8ef
}
TD.TableBody1 {
LINE-HEIGHT: normal; BACKGROUND-COLOR: #ffffff
}
TD.TableBody2 {
LINE-HEIGHT: normal; BACKGROUND-COLOR: #e4e8ef
}
TD.TableBody3 {
BACKGROUND-COLOR: #6595d6
}
TD.TopDarkNav {
BACKGROUND-IMAGE: url(Skins/Default/css/default/topbg.gif)
}
TD.TopLighNav {
BACKGROUND-IMAGE: url(Skins/Default/css/default/bottombg.gif)
}
TD.TopLighNav1 {
BACKGROUND-IMAGE: url(Skins/Default/css/default/tabs_m_tile.gif)
}
TD.TopLighNav2 {
BACKGROUND-COLOR: #ffffff
}
.tableBorder1 {
BORDER-RIGHT: 1px; BORDER-TOP: 1px; BORDER-LEFT: 1px; WIDTH: 98%; BORDER-BOTTOM: 1px; BACKGROUND-COLOR: #6595d6
}
.tableBorder2 {
BORDER-RIGHT: #dedede 1px solid; BORDER-TOP: #dedede 1px solid; BORDER-LEFT: #dedede 1px solid; WIDTH: 98%; BORDER-BOTTOM: #dedede 1px solid; BACKGROUND-COLOR: #efefef
}
.tableBorder3 {
BORDER-RIGHT: #fcfcfc 1px solid; BORDER-TOP: #fcfcfc 1px solid; BORDER-LEFT: #fcfcfc 1px solid; WIDTH: 98%; BORDER-BOTTOM: #fcfcfc 1px solid; BACKGROUND-COLOR: #f0fbfd
}
.tableBorder3 {
BORDER-RIGHT: #6595d6 1px solid; BORDER-TOP: 0px; BORDER-LEFT: #6595d6 1px solid; WIDTH: 98%; BORDER-BOTTOM: 0px
}
.tableBorder4 {
BORDER-RIGHT: #6595d6 1px solid; BORDER-TOP: #6595d6 1px solid; BORDER-LEFT: #6595d6 1px solid; WIDTH: 98%; BORDER-BOTTOM: #6595d6 1px solid
}
#TableTitleLink A:link {
COLOR: #ffffff; TEXT-DECORATION: none
}
#TableTitleLink A:visited {
COLOR: #ffffff; TEXT-DECORATION: none
}
#TableTitleLink A:active {
COLOR: #ffffff; TEXT-DECORATION: none
}
#TableTitleLink A:hover {
COLOR: #ffffff; TEXT-DECORATION: underline
}
INPUT {
FONT-SIZE: 12px; COLOR: #000000; LINE-HEIGHT: 15px; FONT-FAMILY: Tahoma,Verdana,"宋体"
}
SELECT {
FONT-SIZE: 12px; COLOR: #000000; LINE-HEIGHT: 15px; FONT-FAMILY: Tahoma,Verdana,"宋体"
}
TEXTAREA {
FONT-SIZE: 12px; COLOR: #000000; LINE-HEIGHT: 15px; FONT-FAMILY: Tahoma,Verdana,"宋体"
}
OPTION {
FONT-SIZE: 12px; COLOR: #000000; LINE-HEIGHT: 15px; FONT-FAMILY: Tahoma,Verdana,"宋体"
}
.normalTextSmall {
FONT-SIZE: 11px; COLOR: #000000; FONT-FAMILY: Verdana, Arial, Helvetica, sans-serif
}
.menuskin {
BORDER-RIGHT: #666666 1px solid; BORDER-TOP: #666666 1px solid; BACKGROUND-IMAGE: url(Skins/Default/dvmenubg3.gif); VISIBILITY: hidden; FONT: 12px Verdana; BORDER-LEFT: #666666 1px solid; BORDER-BOTTOM: #666666 1px solid; BACKGROUND-REPEAT: repeat-y; POSITION: absolute; BACKGROUND-COLOR: #efefef
}
.menuskin A {
PADDING-RIGHT: 10px; PADDING-LEFT: 25px; COLOR: black; TEXT-DECORATION: none
}
#mouseoverstyle {
BORDER-RIGHT: #597db5 1px solid; PADDING-RIGHT: 0px; BORDER-TOP: #597db5 1px solid; PADDING-LEFT: 0px; PADDING-BOTTOM: 0px; MARGIN: 2px; BORDER-LEFT: #597db5 1px solid; PADDING-TOP: 0px; BORDER-BOTTOM: #597db5 1px solid; BACKGROUND-COLOR: #c9d5e7
}
#mouseoverstyle A {
COLOR: black
}
.menuitems {
PADDING-RIGHT: 1px; PADDING-LEFT: 1px; PADDING-BOTTOM: 1px; MARGIN: 2px; WORD-BREAK: keep-all; PADDING-TOP: 1px
}
A.navlink:link {
COLOR: #000000; TEXT-DECORATION: none
}
A.navlink:visited {
COLOR: #000000; TEXT-DECORATION: none
}
A.navlink:hover {
COLOR: #003399; TEXT-DECORATION: none
}
.BrightClass {
BACKGROUND-COLOR: #d7d7d7
}
.Redfont {
COLOR: red
}
.ImgOnclick {
}
DIV.quote {
BORDER-RIGHT: #cccccc 1px solid; PADDING-RIGHT: 5px; BORDER-TOP: #cccccc 1px solid; PADDING-LEFT: 5px; BACKGROUND: #f3f3f3; PADDING-BOTTOM: 5px; MARGIN: 5px 20px; BORDER-LEFT: #cccccc 1px solid; LINE-HEIGHT: normal; PADDING-TOP: 5px; BORDER-BOTTOM: #cccccc 1px solid
}
DIV.HtmlCode {
BORDER-RIGHT: #cccccc 1px solid; PADDING-RIGHT: 5px; BORDER-TOP: #cccccc 1px solid; PADDING-LEFT: 5px; FONT-WEIGHT: bold; FONT-SIZE: 14px; BACKGROUND: #fdfddf; PADDING-BOTTOM: 5px; MARGIN: 5px 20px; BORDER-LEFT: #cccccc 1px solid; LINE-HEIGHT: normal; PADDING-TOP: 5px; BORDER-BOTTOM: #cccccc 1px solid; FONT-STYLE: oblique; FONT-FAMILY: Tahoma
}
DIV.info {
PADDING-RIGHT: 5px; BORDER-TOP: #cccccc 1px dotted; PADDING-LEFT: 5px; PADDING-BOTTOM: 5px; MARGIN: 5px 20px; WIDTH: 100%; COLOR: #c5c5c5; LINE-HEIGHT: normal; PADDING-TOP: 5px
}
FONT.ShowTools {
COLOR: white; BACKGROUND-COLOR: #b88ffc
}
</STYLE>
<!--论坛页面开始代码-->
<SCRIPT language=JavaScript src="上大_net-0-1背包问题(回朔法).files/Main.js"></SCRIPT>
</HEAD>
<BODY leftMargin=0 topMargin=0>
<DIV class=menuskin id=popmenu
onmouseover="clearhidemenu();highlightmenu(event,'on')"
style="Z-INDEX: 100; FILTER: alpha(opacity=78)"
onmouseout="highlightmenu(event,'off');dynamichide(event)"></DIV><!--printpage.asp##帖子可打印页面-->
<TABLE style="TABLE-LAYOUT: fixed; WORD-BREAK: break-all" width="98%"
align=center border=0>
<TBODY>
<TR>
<TD vAlign=center
align=top><B>以文本方式查看主题</B><BR><BR>- <B>上大.net</B> (http://www.shangda.net/index.asp)<BR>-- <B>computer
technology</B> (http://www.shangda.net/list.asp?boardid=110)<BR>---- <B>0/1背包问题(回朔法)</B> (http://www.shangda.net/dispbbs.asp?boardid=110&id=48550)<BR>
<HR>
</TD></TR><!--printpage.asp##{$bbslist}循环部分-->
<TR>
<TD vAlign=center
align=top>-- 作者：robinkin<BR>-- 发布时间：2004-10-28
12:56:09<BR><BR>-- 0/1背包问题(回朔法)<BR><FONT color=#0000ff>0/1背包问题
<P></P></FONT>
<P align=left>0 / 1背包问题是一个N P<I>-</I>复杂问题，为了解决该问题，在1 . 4节采用了贪婪算法，在3 .
2节又采用了动态规划算法。在本节，将用回溯算法解决该问题。既然想选择一个对象的子集，将它们装入背包，以便获得的收益最大，则解空间应组织成子集树的形状（如图1
6 - 2所示）。该回溯算法与4 .
2节的装载问题很类似。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。
<P></P>
<P></P>
<P align=left>与程序1 6 -
2一样，左孩子表示一个可行的节点，无论何时都要移动到它；当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是令<I>r
</I>为还未遍历的对象的收益之和，将<I>r </I>加到<I>c p</I>（当前节点所获收益）之上，若（ <I>r + c
p</I>）≤<I>b e s t p</I>（目前最优解的收益），则不需搜索右子树。一种更有效的方法是按收益密度<I>p</I><I>i
</I><I>/ w</I><I>i
</I>对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量，当遇到第一个不能全部放入背包的对象时，就使用它的一部分。
<P></P>
<P></P>
<P align=left><B>例4</B><B>-7 </B>考察一个背包例子： <I>n</I>= 4，<I>c</I>=
7，<I>p</I>= [ 9 , 1 0 , 7 , 4 ]，<I>w</I>= [ 3 , 5 , 2 , 1 ]。这些对象的收益密度为[ 3
, 2 , 3 . 5 , 4
]。当背包以密度递减的顺序被填充时，对象4首先被填充，然后是对象3、对象1。在这三个对象被装入背包之后，剩余容量为1。这个容量可容纳对象2的0 .
2倍的重量。将0 . 2倍的该对象装入，产生了收益值2。被构造的解为<I>x</I>= [ 1 , 0 . 2 , 1 , 1 ]，相应的收益值为2
2。尽管该解不可行（<I>x</I>2 是0 . 2，而实际上它应为0或1），但它的收益值2 2一定不少于要求的最优解。因此，该0 /
1背包问题没有收益值多于2 2的解。
<P></P>
<P></P>
<P align=left>解空间树为图1 6 - 2再加上一层节点。当位于解空间树的节点B时，<I>x</I>1= 1，目前获益为<I>c
p</I>= 9。该节点所用容量为<I>c w</I>= 3。要获得最好的附加收益，要以密度递减的顺序填充剩余容量<I>c l e f
t</I>=<I>ccw</I>= 4。也就是说，先放对象4，然后是对象3，然后是对象2的0 .
2倍的重量。因此，子树<I>A</I>的最优解的收益值至多为2 2。当位于节点<I>C</I>时，<I>c p</I>=<I>c w</I>=
0，<I>c l e f t</I>= 7。按密度递减顺序填充剩余容量，则对象4和3被装入。然后是对象2的0 . 8倍被装入。这样产生出收益值1
9。在子树<I>C</I>中没有节点可产生出比1 9还大的收益值。
<P></P>
<P></P>
<P align=left>在节点E，<I>c p</I>= 9，<I>c w</I>= 3，<I>c l e f t</I>=
4。仅剩对象3和4要被考虑。当对象按密度递减的顺序被考虑时，对象4先被装入，然后是对象3。所以在子树<I>E</I>中无节点有多于<I>c
p</I>+ 4 + 7 = 2 0的收益值。如果已经找到了一个具有收益值2 0或更多的解，则无必要去搜索<I>E</I>子树。
<P></P>
<P></P>
<P align=left>一种实现限界函数的好方法是首先将对象按密度排序。假定已经做了这样的排序。定义类K n a p（见程序1 6 -
5）来减少限界函数B o u n d（见程序1 6 - 6）及递归函数K n a p s a c k（见程序1 6 -
7）的参数数量，该递归函数用于计算最优解的收益值。参数的减少又可引起递归栈空间的减少以及每一个K n a p s a c
k的执行时间的减少。注意函数K n a p s a c k和函数m a x L o a d i n g（见程序1 6 -
2）的相似性。同时注意仅当向右孩子移动时，限界函数才被计算。当向左孩子移动时，左孩子的限界函数的值与其父节点相同。
<P></P>
<P></P>
<P align=left>程序16-5 Knap类
<P></P>
<P></P>
<P align=left>template<class Tw, class Tp>
<P></P>
<P></P>
<P align=left>class Knap {
<P></P>
<P></P>
<P align=left>friend Tp Knapsack(Tp *, Tw *, Tw, int);
<P></P>
<P></P>
<P align=left>p r i v a t e :
<P></P>
<P></P>
<P align=left>Tp Bound(int i);
<P></P>
<P></P>
<P align=left>void Knapsack(int i);
<P></P>
<P></P>
<P align=left>Tw c; / /背包容量
<P></P>
<P></P>
<P align=left>int n; // 对象数目
<P></P>
<P></P>
<P align=left>Tw *w; // 对象重量的数组
<P></P>
<P></P>
<P align=left>Tp *p; // 对象收益的数组
<P></P>
<P></P>
<P align=left>Tw cw; // 当前背包的重量
<P></P>
<P></P>
<P align=left>Tp cp; // 当前背包的收益
<P></P>
<P></P>
<P align=left>Tp bestp; // 迄今最大的收益
<P></P>
<P></P>
<P align=left>} ;
<P></P>
<P></P>
<P align=left>程序16-6 限界函数
<P></P>
<P></P>
<P align=left>template<class Tw, class Tp>
<P></P>
<P></P>
<P align=left>Tp Knap<Tw, Tp>::Bound(int i)
<P></P>
<P></P>
<P align=left>{// 返回子树中最优叶子的上限值Return upper bound on value of
<P></P>
<P></P>
<P align=left>// best leaf in subtree.
<P></P>
<P></P>
<P align=left>Tw cleft = c - cw; // 剩余容量
<P></P>
<P></P>
<P align=left>Tp b = cp; // 收益的界限
<P></P>
<P></P>
<P align=left>// 按照收益密度的次序装填剩余容量
<P></P>
<P></P>
<P align=left>while (i <= n && w[i] <= cleft) {
<P></P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -