﻿<?xml version="1.0" encoding="utf-8" standalone="yes"?><rss version="2.0" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:trackback="http://madskills.com/public/xml/rss/module/trackback/" xmlns:wfw="http://wellformedweb.org/CommentAPI/" xmlns:slash="http://purl.org/rss/1.0/modules/slash/"><channel><title>C++博客-PIGWORLD</title><link>http://www.cppblog.com/Pigwen/</link><description>学无止境</description><language>zh-cn</language><lastBuildDate>Mon, 06 Apr 2026 03:21:36 GMT</lastBuildDate><pubDate>Mon, 06 Apr 2026 03:21:36 GMT</pubDate><ttl>60</ttl><item><title>但愿人长久 千里共婵娟</title><link>http://www.cppblog.com/Pigwen/archive/2006/02/12/3218.html</link><dc:creator>PIGWORLD</dc:creator><author>PIGWORLD</author><pubDate>Sun, 12 Feb 2006 12:48:00 GMT</pubDate><guid>http://www.cppblog.com/Pigwen/archive/2006/02/12/3218.html</guid><wfw:comment>http://www.cppblog.com/Pigwen/comments/3218.html</wfw:comment><comments>http://www.cppblog.com/Pigwen/archive/2006/02/12/3218.html#Feedback</comments><slash:comments>5</slash:comments><wfw:commentRss>http://www.cppblog.com/Pigwen/comments/commentRss/3218.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/Pigwen/services/trackbacks/3218.html</trackback:ping><description><![CDATA[<P align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 今天开google主页的时候看到这篇文章的，来源于<A href="http://blog.joycode.com/zhanbos/articles/67129.aspx">http://blog.joycode.com/zhanbos/articles/67129.aspx</A>。需要说明的是上面blog也是引用别人的，所以我也不知道这篇文章的具体来源，只知道作者是<STRONG>女子嫣然。</STRONG>感谢作者为大家带来这优美的字句，情人节来临前夕，贴上这篇诗意绵绵的文章，祝愿各位程序员朋友，各位生活中的朋友，各位尚单身的朋友，各位已拥有爱情的朋友，情人节快乐！<BR><BR><FONT color=#ff0000 size=5><STRONG><FONT color=#ffa500>标题：但愿人长久 千里共婵娟<BR></FONT></STRONG><FONT color=#ffa500><FONT size=4>作者：女子嫣然</FONT><BR></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 又是一年中秋夜，不知又要惹起世人多少相思愁...... <BR>但愿人长长久 千里共婵娟...... </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 一个人来到这个未知的世上，要经历多少呢？那些曾经经历过的——曾经得到过的、曾经失去的、至今还陪伴在我们身边的。想想吧，前世五百年的回眸才换来今生的擦肩而过，前世千年的等待、千年的柔情啊，才换来对方不知道的片刻温存！！所以，我们该要何等的惜缘啊！不要刻意追求那么多，不要苛求难实现的！就让一切美丽着吧！ </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 有人说，错过的总是最好的，失去的都是最珍贵的，放弃的都是不忍的。 </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>有人说，爱，不如相知，与其执著痴念，不如化为祝福。不要让你爱的人，被你的爱所磨蚀；反过来，以你的爱，让他得到力量，展翅高飞！就算分隔两地，心仍会在一起。 </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 有人说，真正爱一个人，必定以他的幸福，当作是你的幸福。若然有人，能比你给予他更大的幸福，你就把他送到那里去。 </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 有人说，爱情是个模糊的概念，没有人去测量过爱情的长度。也没有任何人得到过具体的结果。如果假定爱情的全程为1公里。那么爱与不爱的距离只有四分之一米。短暂而遥远的旅途。一堵墙的距离，一堵看不见摸不到却实实在在的存在的墙，夹在爱与不爱之间。爱人就在眼前，但无力去拥抱。爱人就在隔壁，在空气中隔离。半步的距离，那怎么也迈不出去的的半步。爱了，勇敢的去追寻，却碰了壁。不爱，毅然的想离去，发现迷了路。原来爱与不爱同在一个屋檐下，如同长椅两边的坐客，只有短短的隔距，然而好象只是一场巧遇，因为疲惫找寻到同一个歇脚处。离去时相眸一眼，意识到这是莫名的缘分，却走向相反的方向。也许面对爱的时候，不爱就站在背后注视着转身的瞬间，当转身与不爱相视的时候，爱依然伫立，流泪，惋惜……原来爱与不爱之间的四分之一米的距离就是自己的身躯…… </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;只有前世有约的人，今生才能相随。 </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;这世上有谁在凭栏？盈盈横塘畔的楼台上，倚着朱红的栏杆，不经意却是很美地在笑，这个时候我便想起诗书上的话：巧笑倩兮，美目盼兮。说的，就是我罢？ </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;这世上，有谁在走？也许，那就是你吧？苍凉景物，滚滚红尘，一袭青衫，奔波在如烟的暮雨中，斜斜的伞，遮着黄昏细雨。一条青色砖石路铺就的深巷，由远及近，独自彷徨在悠长，悠长又寂寥的雨巷，希望飘过一个丁香一样地结着愁怨的姑娘。 </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 一种无从提问无从回答的感觉。 </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;是一种预感的实现，是一种冥冥之中的昭示，不曾谋面，又似曾相识。 </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;是永恒也是刹那，是真实也是虚幻，这世间有我不曾明白的神秘。 </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;轮回中，终于不期然地遇见。在茫茫人海。心与心之间，一下子就没了距离。 假如有一种时刻觉得美好，那一定是谁穿越时空的祝福。 </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;缘，不是说来就来，却是说走就走的！所以，隔岸而立，所有的美丽因相望而成缘，所有的无奈因相忘而失缘。我们最终都注定要迷失在永恒的轮回之中。 </STRONG></FONT></P>
<P><FONT color=#ffa500 size=3><STRONG>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 只有前世有约的人，今生才能相随。 </STRONG></FONT></P>
<P><STRONG><FONT color=#ffa500><FONT size=3>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 菩提树下，也许终于有一天，我们会领悟这</FONT><FONT size=3>——如梦的尘缘。 </FONT></FONT></STRONG></P>
<P><STRONG><FONT color=#ffa500><FONT size=3>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 前世积攒多少次的回眸啊，才能换得相识？甚至相知？甚至相爱？</FONT><BR></FONT></STRONG></P></FONT><img src ="http://www.cppblog.com/Pigwen/aggbug/3218.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/Pigwen/" target="_blank">PIGWORLD</a> 2006-02-12 20:48 <a href="http://www.cppblog.com/Pigwen/archive/2006/02/12/3218.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>传说中月薪3万的面试题</title><link>http://www.cppblog.com/Pigwen/archive/2006/02/06/3085.html</link><dc:creator>PIGWORLD</dc:creator><author>PIGWORLD</author><pubDate>Mon, 06 Feb 2006 03:58:00 GMT</pubDate><guid>http://www.cppblog.com/Pigwen/archive/2006/02/06/3085.html</guid><wfw:comment>http://www.cppblog.com/Pigwen/comments/3085.html</wfw:comment><comments>http://www.cppblog.com/Pigwen/archive/2006/02/06/3085.html#Feedback</comments><slash:comments>10</slash:comments><wfw:commentRss>http://www.cppblog.com/Pigwen/comments/commentRss/3085.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/Pigwen/services/trackbacks/3085.html</trackback:ping><description><![CDATA[<FONT size=6><STRONG>猫扑上看到的一道面试题，大家讨论讨论：</STRONG></FONT><BR>张老师的生日是M月N日， <BR>2人都知道张老师的生日是下列10组中的一天， <BR>张老师把M值告诉了小明，把N值告诉了小强， <BR>张老师问他们知道他的生日是那一天吗？ <BR>3月4日 3月5日 3月8日 <BR>6月4日 6月7日 <BR>9月1日 9月5日 <BR>12月1日 12月2日 12月8日 <BR>小明说：如果我不知道的话，小强肯定也不知道 <BR>小强说：本来我也不知道，但是现在我知道了 <BR>小明说：哦，那我也知道了 <BR>请根据以上对话推断出张老师的生日是哪一天<BR><BR>看了一下猫扑上的分析，答案主要集中在6月4号和9月1号的争论。个人认为是9月1号哈。<BR><img src ="http://www.cppblog.com/Pigwen/aggbug/3085.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/Pigwen/" target="_blank">PIGWORLD</a> 2006-02-06 11:58 <a href="http://www.cppblog.com/Pigwen/archive/2006/02/06/3085.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>翻译《UNIX环境高级编程（第二版）》</title><link>http://www.cppblog.com/Pigwen/archive/2006/01/04/2424.html</link><dc:creator>PIGWORLD</dc:creator><author>PIGWORLD</author><pubDate>Wed, 04 Jan 2006 04:31:00 GMT</pubDate><guid>http://www.cppblog.com/Pigwen/archive/2006/01/04/2424.html</guid><wfw:comment>http://www.cppblog.com/Pigwen/comments/2424.html</wfw:comment><comments>http://www.cppblog.com/Pigwen/archive/2006/01/04/2424.html#Feedback</comments><slash:comments>4</slash:comments><wfw:commentRss>http://www.cppblog.com/Pigwen/comments/commentRss/2424.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/Pigwen/services/trackbacks/2424.html</trackback:ping><description><![CDATA[<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 对UNIX程序设计很不了解，希望通过慢慢翻译这本书，一方面学习UNIX系统程序设计，一方面锻炼自己的英语能力！<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 欢迎大家指出我翻译不正确的地方，哪怕是一小点点都十分感谢！<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <A HREF="/Pigwen/category/710.html">点击这里查看《UNIX环境高级编程（第二版）》翻译。</A></P><img src ="http://www.cppblog.com/Pigwen/aggbug/2424.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/Pigwen/" target="_blank">PIGWORLD</a> 2006-01-04 12:31 <a href="http://www.cppblog.com/Pigwen/archive/2006/01/04/2424.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>背包问题 －－ 2) 改进，自顶向下的动态编程</title><link>http://www.cppblog.com/Pigwen/archive/2006/01/03/2413.html</link><dc:creator>PIGWORLD</dc:creator><author>PIGWORLD</author><pubDate>Tue, 03 Jan 2006 15:16:00 GMT</pubDate><guid>http://www.cppblog.com/Pigwen/archive/2006/01/03/2413.html</guid><wfw:comment>http://www.cppblog.com/Pigwen/comments/2413.html</wfw:comment><comments>http://www.cppblog.com/Pigwen/archive/2006/01/03/2413.html#Feedback</comments><slash:comments>3</slash:comments><wfw:commentRss>http://www.cppblog.com/Pigwen/comments/commentRss/2413.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/Pigwen/services/trackbacks/2413.html</trackback:ping><description><![CDATA[<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 在上一篇《<A HREF="/Pigwen/archive/2006/01/03/2412.html" target=_blank><EM>背包问题 －－ 1) 思路，递归求解</EM></A>》中，我们讨论了用递归的方式来解决背包问题。但是，直接使用递归会造成大量的重复运算，就上一篇中的例子来说，对于容积为17的背包来说，其中两种组合方案为：</P>
<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 方案一：&nbsp;4(A) + 5(B) = 9 ，即背包中装一个A物品和一个B物品；</P>
<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 方案二： 5(B) + 10(C) = 15 ，即背包中装一个B物品和一个C物品；</P>
<P>注意，上面两种方案都需要计算knap(space = cap - item[1].size)（注：1对应B物品）的情况，这就造成了重复计算，而且计算量是成指数增长的。如果我们在第一次计算knap(space = cap - item[1].size)时就保存其返回值，那么在下一次需要用到的时候只需要直接使用这个返回值就行了，而不必再去计算。</P>
<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 这里我们给出动态编程的定义，即<STRONG>递归程序中，在每一步递归调用前使用已计算的值来完成当前的递归调用</STRONG>。</P>
<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 对于背包问题，我们用一个数组knowKnap[M]来保存每一个可能的space值。按动态编程改进后的程序源代码如下：</P>
<P><IMG alt=http://pigworld.blogbus.com/files/1135354918.jpg hspace=0 src="http://pigworld.blogbus.com/files/1135354918.jpg" align=baseline border=0></P><img src ="http://www.cppblog.com/Pigwen/aggbug/2413.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/Pigwen/" target="_blank">PIGWORLD</a> 2006-01-03 23:16 <a href="http://www.cppblog.com/Pigwen/archive/2006/01/03/2413.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>背包问题 －－ 1) 思路，递归求解</title><link>http://www.cppblog.com/Pigwen/archive/2006/01/03/2412.html</link><dc:creator>PIGWORLD</dc:creator><author>PIGWORLD</author><pubDate>Tue, 03 Jan 2006 15:15:00 GMT</pubDate><guid>http://www.cppblog.com/Pigwen/archive/2006/01/03/2412.html</guid><wfw:comment>http://www.cppblog.com/Pigwen/comments/2412.html</wfw:comment><comments>http://www.cppblog.com/Pigwen/archive/2006/01/03/2412.html#Feedback</comments><slash:comments>5</slash:comments><wfw:commentRss>http://www.cppblog.com/Pigwen/comments/commentRss/2412.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/Pigwen/services/trackbacks/2412.html</trackback:ping><description><![CDATA[<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 最近看了《算法I－IV（C++语言描述）》中关于动态编程求解背包问题的部分，感觉书中描述的不是很详细，在这里通过我个人的理解再加上书中的描述，再重温下这一经典问题的动态编程求解方法。</P>
<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 所谓的背包问题，可以描述如下：一个小偷打劫一个保险箱，发现柜子里有N类不同大小与价值的物品，但小偷只有一个容积为M的背包来装东西，背包问题就是要找出一个小偷选择所偷物品的组合，以使偷走的物品总价值最大。我们可以定义以下结构：</P>
<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; struct Item {<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int size;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //保存物品大小<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int val;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //保存物品价值<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; };</P>
<P>例如有下表中的物品：</P>
<DIV align=right>
<TABLE borderColor=#000000 cellSpacing=0 cellPadding=4 width=607 border=1>
<COLGROUP>
<COL width=63>
<COL width=99>
<COL width=99>
<COL width=99>
<COL width=99>
<COL width=98></COLGROUP>
<THEAD>
<TR vAlign=top>
<TH width=63 height=17>
<P style="FONT-STYLE: normal"><FONT face="Times New Roman, serif"><B>Index</B></FONT></P></TH>
<TH width=99>
<P style="FONT-STYLE: normal"><FONT color=#0000ff><FONT face="Times New Roman, serif">0</FONT></FONT></P></TH>
<TH width=99>
<P style="FONT-STYLE: normal"><FONT color=#0000ff><FONT face="Times New Roman, serif">1</FONT></FONT></P></TH>
<TH width=99>
<P style="FONT-STYLE: normal"><FONT color=#0000ff><FONT face="Times New Roman, serif">2</FONT></FONT></P></TH>
<TH width=99>
<P style="FONT-STYLE: normal"><FONT color=#0000ff><FONT face="Times New Roman, serif">3</FONT></FONT></P></TH>
<TH width=98>
<P style="FONT-STYLE: normal"><FONT color=#0000ff><FONT face="Times New Roman, serif">4</FONT></FONT></P></TH></TR></THEAD>
<TBODY>
<TR vAlign=top>
<TD width=63 height=18>
<P align=center><FONT face="Times New Roman, serif"><B>Item</B></FONT></P></TD>
<TD width=99>
<P align=center><FONT color=#00ff00><FONT face="Times New Roman, serif">A</FONT></FONT></P></TD>
<TD width=99>
<P align=center><FONT color=#00ff00><FONT face="Times New Roman, serif">B</FONT></FONT></P></TD>
<TD width=99>
<P align=center><FONT color=#00ff00><FONT face="Times New Roman, serif">C</FONT></FONT></P></TD>
<TD width=99>
<P align=center><FONT color=#00ff00><FONT face="Times New Roman, serif">D</FONT></FONT></P></TD>
<TD width=98>
<P align=center><FONT color=#00ff00><FONT face="Times New Roman, serif">E</FONT></FONT></P></TD></TR>
<TR vAlign=top>
<TD width=63 height=18>
<P align=center><FONT face="Times New Roman, serif"><B>Size</B></FONT></P></TD>
<TD width=99>
<P align=center><FONT color=#ff3366><FONT face="Times New Roman, serif">3</FONT></FONT></P></TD>
<TD width=99>
<P align=center><FONT color=#ff3366><FONT face="Times New Roman, serif">4</FONT></FONT></P></TD>
<TD width=99>
<P align=center><FONT color=#ff3366><FONT face="Times New Roman, serif">7</FONT></FONT></P></TD>
<TD width=99>
<P align=center><FONT color=#ff3366><FONT face="Times New Roman, serif">8</FONT></FONT></P></TD>
<TD width=98>
<P align=center><FONT color=#ff3366><FONT face="Times New Roman, serif">9</FONT></FONT></P></TD></TR>
<TR vAlign=top>
<TD width=63 height=17>
<P align=center><FONT face="Times New Roman, serif"><B>Val</B></FONT></P></TD>
<TD width=99>
<P align=center><FONT color=#ff3366><FONT face="Times New Roman, serif">4</FONT></FONT></P></TD>
<TD width=99>
<P align=center><FONT color=#ff3366><FONT face="Times New Roman, serif">5</FONT></FONT></P></TD>
<TD width=99>
<P align=center><FONT color=#ff3366><FONT face="Times New Roman, serif">10</FONT></FONT></P></TD>
<TD width=99>
<P align=center><FONT color=#ff3366><FONT face="Times New Roman, serif">11</FONT></FONT></P></TD>
<TD width=98>
<P align=center><FONT color=#ff3366><FONT face="Times New Roman, serif">13</FONT></FONT></P></TD></TR></TBODY></TABLE></DIV>
<DIV align=left></DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 上表中第一行（Index）是物品在程序中的索引号，第二行（Item）是物品的标示，第三行（Size）是物品的大小，第四行（Val）是物品的价值，而每一列又对应了一类物品。假设小偷背包的容积为17，则小偷能够拿走5个A价值为20的物品，或者1个D和1个E，价值为24的物品，等等。</DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 为了使小偷在背包容积为cap的情况下，能够偷走最大价值的物品，我们可以假设小偷足够聪明，无论背包容积cap为多少，小偷总能找到最优的组合使背包中所装物品的价值最大。</DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 倘若我们定义函数：</DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int&nbsp; knap( int cap );</DIV>
<DIV align=left>该函数的返回值为容积为cap的背包所装物品的最大价值。对于cap为17的背包，因为有5类物品，所以所装物品的价值有以下组合：</DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1） 4 + knap( 17 - 3 )，即 item[0].val + knap(cap&nbsp;- item[0].size);</DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2)&nbsp;&nbsp;&nbsp;&nbsp; 5 + knap( 17 - 4 )，即 item[1].val + knap(cap - item[1].size);</DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 3)&nbsp;&nbsp;&nbsp; 10 + knap( 17 - 7 )，即 item[2].val + knap(cap - item[2].size);</DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 4)&nbsp;&nbsp;&nbsp;&nbsp; 11 + knap( 17 - 8 )，即 item[3].val + knap(cap - item[3].size);</DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 5)&nbsp;&nbsp;&nbsp;&nbsp; 13 + knap( 17 - 9 )，即 item[4].val + knap(cap - item[4].size);</DIV>
<DIV align=left>因为小偷已经帮助我们找到了cap = cap - item[i].size的最优组合，所以我们只需要找到item[i].val + knap(cap - item[i].size)的最大值也就完称了我们的任务了。</DIV>
<DIV align=left></DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 下面的程序代码是按以上的思路编写的：</DIV>
<DIV align=left>&nbsp;<IMG alt=http://pigworld.blogbus.com/files/1134918024.jpg hspace=0 src="http://pigworld.blogbus.com/files/1134918024.jpg" align=baseline border=0></DIV>
<DIV align=left>我么定义了一个类型为Item的N项数组，对于每一个可能的项，我们递归的计算所能得到的最大值，然后挑出那些值中的最大项返回。</DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 需要说明的是，上面的代码不应该成为正式的代码，如果按上面的代码画出每次函数调用的二叉树图，就会发现有大量重复的计算来处理同一个问题，其结果就是耗费指数级的时间，因而是低效的。</DIV>
<DIV align=left>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 下一篇<EM>《</EM><A HREF="/Pigwen/archive/2006/01/03/2413.html"><FONT color=#003333><EM>背包问题 －－ 2) 改进，自顶向下的动态编程</EM></FONT></A><EM>》</EM>将会介绍如何对上面的代码改进，使耗费的时间从指数级减少到线性级。</DIV><img src ="http://www.cppblog.com/Pigwen/aggbug/2412.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/Pigwen/" target="_blank">PIGWORLD</a> 2006-01-03 23:15 <a href="http://www.cppblog.com/Pigwen/archive/2006/01/03/2412.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item></channel></rss>