动态规划是本书介绍的五种算法设计方法中难度最大的一种，它建立在最优原则的基础上。采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。在介绍动态规划的原理之后，本章将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。
3.1 算法思想
和贪婪算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在

君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计过程中。本章将首先介绍怎样在算法设计领域应用这一古老的策略，然后将利用这一策略解决如下问题：最小最大问题、矩阵乘法、残缺棋盘、排序、选择和计算一个几何问题——找出二维空间中距离最近的两个点。
本章给出了用来分析分而治之算法复杂性的数学方法，并通过推导最小最大问题和排序问题的复杂性下限来证明分而治之算法对于求解这两种问题是最优的（因为算法的复杂性与下限一致）。
2.1 算法思想

　　任何美好的事情都有结束的时候。现在我们学习的是本书的最后一章。幸运的是，本章用到的大部分概念在前面各章中已作了介绍。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间（常用的树结构是第1 6章所介绍的子集树和排列树）。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。本章与第1 6章所考察的应用完全相同，因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容

　　寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少

　　 虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。
    本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货箱装船问题、背包问题

把计算机科学与进化论结合起来的尝试始于50年代末，但由于缺乏一种通用的编码方案
，人们只能依赖变异而非交配来产生新的基因结构，故而收效甚微。到60年代中期，美
国Michigan大学的John Hol－land在A．S．Fraser和H．J．Bremermann等人工作的基础
上提出了位串编码技术。这种编码既适于变异操作，又适于交配（即杂交）操作，并且
强调将交配作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应
行为的研究中，并于1975年

这个程序可以算当一个人知道和，另一个人知道积的时候的
各种对话以后的结果。
目前的设置是计算和前述的题目一样的情况。
程序头上的RANGE_MIN和RANGE_MAX为取数字的范围。
SAME为两个数字是否可以相等。
程序尾部的一系列调用就是对话的过程。
talk函数的三个参数分别是：
1.是否是知道和的那个人说的话
2.说话中的对象是否是知道和的那个人
3.那个对象是被断言知道还是不知道。
比如：
p说我不知道，就是true,t

1. Odd: Siamese method
  It begins by placing a "1" in any location (in the center square of the
  top row in the above example), then incrementally placing ubsequent
  numbers in the square one unit above and to the right. Th

☆──────────────────────────────────────☆
    ender (ender) 于 Mon Feb 25 13:35

很久以前这里曾讨论过这道题，今天在华南木棉找到一个详细的解释，特灌
一篇， 希望对那些象我一样的菜鸟会有帮助 。
海盗的难题
    数学的逻辑有时会导致看来十分怪异的结论。一般的规则是，如果逻辑
推理没有漏洞， 那么结论就必定站得住脚，即使它与你的直觉矛盾。 1998
年9月，加利福尼亚州帕洛阿 尔托的Stephen M. Omohundro寄给我一道难题，
它恰好就属于这一类。这难题已经流传 了至少十年，但是Omohu

埃及分数问题属于数论的一个分支“丢番图方程”，现在的研究已经比较深入了，不过
仍有很多问题尚未解决。这个题目虽然看起来很简单，但是我们几乎不可能想到一个纯理论
性的方法解决，搜索势在必行。
最基本的搜索方式有深度优先和广度优先。这道题目用深度优先很难出解，因为我们无
法预料找到的地一个解的深度，因此我们考虑有广度优先方法。
暂且不考虑广度优先是否最好，我们先来考虑算法的具体实现。
1.节点类型:
是一个K元组（a1,a2,...ak）, 代表当前解中的分

可以看作这样一个问题,从左下走到右上,
在不走到左上的半个正方形(x的部分)的
情况下,有几种不同的走法.(*为一条可能的路)
xxxxx*
xxxx**
xxx.*.
xx..*.
x****.
**....
则,对于每条不符合要求的路,
取其第一个走入x范围的点,
把之后走的所有步骤的向右
或向上互相对调.
由于刚走入的时候向上一定
比向又多走一步,所以剩下
的一定是向右的多一步.
这样交

称球问题——经典智力题推而广之三

设共有L快区域
证明：由贪心算法求的的这种种法的前i位（1=〈i〈=L）种树的棵数是任何一种可能的
种法中前i位种树棵数最少的种法；设这种种法的前i位种树棵数为Ai（1=〈i〈=L）
取任意一种不是贪心算法种法的可能种法，设它的前i位种树棵树为Bi（1=〈i〈=L）
等价证明
Ai〈=Bi（1=〈i〈=L）
当i=1时，若由贪心算法判断第一棵树可以去掉，A（1）=0〈=B（1）显然满足题设
若判断不可以去掉，说明任何一种种法的第一位都要种树，A

☆──────────────────────────────────────☆
    hotsaucetang (sillybird100) 于 20

请问有没有求 次小生成树（就是代价第2小的） 的比较好的方法？
2000个结点，20000条边，最好能在O(n^2)以内
☆──────────────────────────────────────☆
   

下面是我的严格证明，不过写得比较麻烦：（ 图论里面的很多问题容易理解，但是却不容易用语言表达清楚。
为了阐述清楚证明，首先作如下严格定义：
1。我们用a～b表示树中任意两个结点a,b之间的唯一路径，a～b之间可以有0个或多个结点
；用x \in a～b表示结点x处于路径a,b上，即存在形如a～x～b的路径（这里x可以和a或b
重合）；用符号a-b表示a,b直接相邻。
2。结点之间的距离——根据树的性质，任意两个结点u,v之间都

一、引言
　　问题求解技术，包括两个方面的内容：表示和搜索。在这两个方面的内容中，
搜索是重点，表示是基础。不同的状态表示对搜索的效率会产生极大的影响。一个
粗糙的状态表示可能使得搜索时要对状态变换进行更多的操作，而采取简洁的表示
，搜索时进行的操作可能就显得方便、高效，甚至由于状态表示准确描述了问题的
本质，给人以启示，从而找到更好的搜索技术。动态规划是求解问题的一个重要技
术，它的状态表示在整个算法中有着举足轻重的作用，对整个算法的影响也远比其
他搜

对所有点按 y 坐标排序，枚举一个上界（可以从最大的 y 坐标枚举到最小的）
对每个上界，初始时另下界在具有最小 y 坐标的点上
这时，上下界之间的区域被区域中的点分割为很多小区域（根据这些区域，可以计算出
一个当前的最大矩形）
将下界上移，移到下一个点上时，就把这个点从区域中去掉
去掉这个点后，这个点左右两边的区域就合成一块了。由于上下界距离是变小的，所以
只有这个区域的面积可能大于当前的最大面积，只需要判断这个区域即可（复杂度O(1)
）。

☆──────────────────────────────────────☆
    ConeZXY (小鱼，为看追忆编竟然买DVDROM，彻底穷了) 于

☆──────────────────────────────────────☆
    splutter (呆子) 于 Fri Jun  8

计算几何常用算法概览
一、引言
　　计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，

台湾不能输在起跑点上！
文／林孟仪
摄影／林孟仪
2002年5月 CHEERS杂志
从小选拔、培养、集训，是近年大陆参加世界各种竞赛的标准模式，即使是程序大赛也不
例外。
「奖杯」对一个大陆青年的重要性，是台湾年轻人难以想象的......
晚上9点，夏威夷，几家欢乐几家愁的程序大赛结果揭晓后4个小时。
隔着饭店的房门，可以清楚地听到房间里不时传来年轻人夹杂着几口京片子的笑闹声。刚
打败来自27个国家的64个队伍

http://sports.sina.com.cn2004年08月21日 09:32 齐鲁晚报
 
 
　　记者第一次去位于烟台市福山区东陌堂的唐功红家采访时，唐母王全荣正在村里集
上的肉摊上忙碌着，她擦着额头上的汗说：“小伙子，上午忙啊，下午啥时都有时间！”
村里人都说唐家勤快

创新教育，创造奇迹
--回眸上海交大ACM-ICPC之路
张文清
9年前，当ACM国际大学生程序设计竞赛（以下简称ACM-ICPC）进入中国大陆时，谁也没
有想到是：大陆会以惊人的速度在短短的四五年后几乎席卷由大陆参加的所有亚洲赛区
的冠军，令亚洲其他国家和地区感到畏惧。然而，更大的奇迹在2002年的3月，一个不会
有人敢预言的大陆名校却永远留在了ACM-ICPC世界杯上，三年后的今天，又是这所名校
把这一赛事的决赛入驻中国，同时再一次把这座世界