下载文档原格式
ACM暑期集训报告院系：专业：年级：学号：姓名：日期：西南交通大学目录目录 (1)第1章动态规划（dp） (2)1.1 简介 (2)1.2 教师内容 (5)1.3 基本dp——背包问题 (6)1.4若干经典dp及常见优化 (9)1.5类似题目 (10)参考文献 (31)附录1 暑期集训心得体会 (31)第1章动态规划（dp）（标题采用2号黑体居中，下空1行）1.1 简介（标题采用四号黑体，正文内容采用小四号字体，1.5倍行距）在解决问题的时候我们经常遇到这种问题：在多种方式的操作下我们如何得到一个最优的方式让我们得到满意的结果。
这时候我们大多人的思想就是贪心。
不错贪心确实是一个不错的算法，首先他简单容易想到，我们在操作起来也比较容易。
现在我推荐几道我们oj上的贪心算法的题：soj1562药品运输soj1585 Climbing mountain。
为了引入动归算法我先拿药品运输这道题简单说一下贪心算法。
示例1：药品运输（题目采用小四号Times New Roman字体）Description5.12大地震后，某灾区急需一批药品，现在有N种药品需要运往灾区，而我们的运输能力有限，现在仅有M辆运输车用来运输这批药品，已知不同的药品对灾区具有不同的作用（“作用”用一个整数表示其大小），不同的药品需要的运输力（必要的车辆运载力）不同，而不同的车辆也具有不同的运输力。
同时，我们希望不同的药品用不同的车辆来运输（避免发生混淆）。
现在请你帮忙设计一方案，来使得运往灾区的药品对灾区的作用最大。
Input第一行包含一个整数T，表示需要处理的测试数据组数。
每一组第一行包括两个整数N,M，分别表示药品总数，及车辆总数。
接着第二行包含N个整数（pi<=10000），分别表示每种药品的作用。
接着第三行包含N个整数，分别表示每种药品必须得运载力(wi<=1000)。
接着第四行包含M个整数，表示每辆车的运输力(c<=1000)；（T<=10; N,M<=1000）Output输出包括T行，每行仅一个整数，表示最大的作用值。
背包九讲P01: 01背包问题题目有N件物品和一个容量为V的背包。
第i件物品的费用是c[i]，价值是w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。
所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。
如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
注意f[i][v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。
所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。
如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[i][v-1]，这样就可以保证f[N] [V]就是最后的答案。
至于为什么这样就可以，由你自己来体会了。
优化空间复杂度以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。
那么，如果只用一个数组f [0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v -c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i -1][v-c[i]]的值。
“
背包的打法有许多种，本人只会三种，但是本人最喜欢以下的这种打法，因为它速度上虽然不如一条龙快，但是却比一条龙牢固可靠----跑5公里时如果背包垮了，那就要抱着被子跑了，多狼狈啊。
所以，”“”
还是这种打法好；速度也不算慢，反正本人在部队时紧急集合的速度通常是5分钟以内出门，还不是最快的。
下面我用实物图片教教不会打背包的兄弟，特别是那些即将去部队的新战友们，大家喜欢的话请支持一下，要是学不会你们砍我，呵呵。
有兴趣的可以拿包烟或是书练练手
一、叠被子：被子要四叠，这样打出来的背包看着才好看精干，平常整内务的三叠打出来呆头呆脑的效果不好；然后把被子折叠成图中形状
二、这是什么？原来是背包带隆重惊艳登场，我通常把它盘成圆饼状，便于存放携带，由于没有宽背包带，就不说它了
三、拆开背包带，如图竖直放在被子上
四、被子翻过来，背包带的一端插入扣里，用力拉紧；然后绕被子一圈，抽紧
五、第一大步骤完成
六、现在开始处理背包下端，用背包带的另一段斜压背包一角，绕下端一圈，抽紧
七、第二大步骤完成
八、现在处理中间，上下多出的带子交叉拉紧（用力！），绕背包一圈，抽紧
九、打结（注意一定要在背包的侧面打结，要是在背面打结的话，跑5公里硌得背部生痛，多出来的带子掖到缝隙里藏好）
十、大功告成！！漂亮不？我手头没有宽背包带，所以背包不完整，见谅！！
铁血, 本贴地址: /post_2426285_1.html。
下面总结一些小小的经验：1、组队很重要，队友们一定要能谈得来（曾经发生一组队员互相不服气，结果各自做各的，成绩就可想而知了），除此之外，队员之间一定要各有所常，建模嘛，无非就是查阅文献，建立模型，分析数据，编程，写文章，较对等等，保证你们组每个人都会有一些强项，当然男女生也应该都是要有的，所谓男女搭配，干活不累，嘿嘿;2、文章整洁很重要。
如果你是评委的话，肯定喜欢写的文章有条理，图文并茂之类的文章，将心比心，抓住评委的心才是最重要。
3、做建模创新很重要。
这么多的文章你的要想脱颖而出，创新也必须的，当然，你可以想你这篇文章结合了什么什么方法，最好把那方法说得天花乱坠，但不可华而不实，这就行啦。
4、摘要很重要。
以前大学生比赛的时候，是先通过摘要就刷一批，我觉得这是很公平的方法，摘要就是说明你这篇文章的特色和结构的，如果摘要我都不愿意看，干嘛花时间看你的正文。
5、人品很重要，还是我那句话，莫要太看重结果，抱着神马都是浮云的心态~~~数模经历入门篇平时有不少人会加我QQ，然后问诸如“什么是数模”“我该怎么学数模”之类的问题。
这里不是不鼓励大家和我讨论，而是有些问题google或baidu一下很容易得到答案，完全没有必要去问学长或老师。
而且使用搜索引擎的能力在数学建模中也是一个非常重要的能力。
这里推荐一些书，建议刚接触数学建模的朋友们看姜启源、谢金星的《数学模型》，这本书比较全面地介绍了数学建模中一些基本的、常用的模型和方法，有很多的例子，可以全面地了解什么是数学模型，也能基本地掌握如何抽象建模等。
希望进一步深入的同学推荐姜启源、谢金星的《数学模型案例集》，这本书里有不少比较有意思的问题，可以尝试自己做一下，难度比正式比赛要差很多，但是对于初学者来说比较容易上手。
也推荐叶其孝的那套黑书，虽然内容有点老，但是有很多比较有意思的解题思路等。
这里推荐一个很不错的数学建模网站：，那里有很多非常不错的学习资料。
对于那些已经有一些数学建模基础的同学则不推荐读叶其孝的那套书，而是可以直接在网上找一些往年国一或是美赛特等的文章，仔细阅读，了解其中的方法，然后自己动手重新做一遍。
NOIP复习资料（C++版）主编葫芦岛市一高中李思洋完成日期2012年8月27日……………………………………………………………最新资料推荐…………………………………………………前言有一天，我整理了NOIP的笔记，并收集了一些经典算法。
不过我感觉到笔记比较凌乱，并且有很多需要修改和补充的内容，于是我又搜集一些资料，包括一些经典习题，在几个月的时间内编写出了《NOIP复习资料》。
由于急于在假期之前打印出来并分发给同校同学（我们学校既没有竞赛班，又没有懂竞赛的老师。
我们大家都是自学党），《NOIP复习资料》有很多的错误，还有一些想收录而未收录的内容。
在“减负”的背景下，暑期放了四十多天的假。
于是我又有机会认真地修订《NOIP复习资料》。
我编写资料的目的有两个：总结我学过（包括没学会）的算法、数据结构等知识；与同学共享NOIP知识，同时使我和大家的RP++。
大家要清醒地认识到，《NOIP复习资料》页数多，是因为程序代码占了很大篇幅。
这里的内容只是信息学的皮毛。
对于我们来说，未来学习的路还很漫长。
基本假设作为自学党，大家应该具有以下知识和能力：①能够熟练地运用C++语言编写程序（或熟练地把C++语言“翻译”成Pascal语言）；②能够阅读代码，理解代码含义，并尝试运用；③对各种算法和数据结构有一定了解，熟悉相关的概念；④学习了高中数学的算法、数列、计数原理，对初等数论有一些了解；⑤有较强的自学能力。
代码约定N、M、MAX、INF是事先定义好的常数（不会在代码中再次定义，除非代码是完整的程序）。
N、M、MAX 针对数据规模而言，比实际最大数据规模大；INF针对取值而言，是一个非常大，但又与int的最大值有一定差距的数，如100000000。
对于不同程序，数组下标的下限也是不同的，有的程序是0，有的程序是1。
阅读程序时要注意。
阅读顺序和方法没听说过NOIP，或对NOIP不甚了解的同学，应该先阅读附录E，以加强对竞赛的了解。
背包问题九讲 2.0 alpha1崔添翼 (Tianyi Cui,a.k.a.dd_engi)September 15,2011本文题为《背包问题九讲》，从属于《动态规划的思考艺术》系列。
这系列文章的第一版于2007年下半年使用EmacsMuse制作，以HTML格式发布到网上，转载众多，有一定影响力。
2011年9月，本系列文章由原作者用L A T E X重新制作并全面修订，您现在看到的是2.0 alpha1版本，修订历史及最新版本请访问https:///tianyicui/ pack查阅。
本文版权归原作者所有，采用CC BY-NC-SA协议发布。
Contents101背包问题21.1题目 (2)1.2基本思路 (2)1.3优化空间复杂度 (3)1.4初始化的细节问题 (3)1.5一个常数优化 (4)1.6小结 (4)2完全背包问题42.1题目 (4)2.2基本思路 (4)2.3一个简单有效的优化 (5)2.4转化为01背包问题求解 (5)2.5O(V N)的算法 (5)2.6小结 (6)3多重背包问题63.1题目 (6)3.2基本算法 (6)3.3转化为01背包问题 (7)3.4O(VN)的算法 (7)3.5小结 (7)4混合三种背包问题84.1问题 (8)4.201背包与完全背包的混合 (8)4.3再加上多重背包 (8)4.4小结 (8)15二维费用的背包问题95.1问题 (9)5.2算法 (9)5.3物品总个数的限制 (9)5.4复整数域上的背包问题 (9)5.5小结 (9)6分组的背包问题106.1问题 (10)6.2算法 (10)6.3小结 (10)7有依赖的背包问题107.1简化的问题 (10)7.2算法 (10)7.3较一般的问题 (11)7.4小结 (11)8泛化物品118.1定义 (11)8.2泛化物品的和 (12)8.3背包问题的泛化物品 (12)8.4小结 (13)9背包问题问法的变化139.1输出方案 (13)9.2输出字典序最小的最优方案 (13)9.3求方案总数 (14)9.4最优方案的总数 (14)9.5求次优解、第K优解 (14)9.6小结 (15)101背包问题1.1题目有N件物品和一个容量为V的背包。
放入第i件物品耗费的空间是C i，得到的价值是W i。
求解将哪些物品装入背包可使价值总和最大。
1.2基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即F[i,v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是：F[i,v]=max{F[i−1,v],F[i−1,v−C i]+W i}这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。
所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包2中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只和前i−1件物品相关的问题。
如果不放第i件物品，那么问题就转化为“前i−1件物品放入容量为v的背包中”，价值为F[i−1,v]；如果放第i件物品，那么问题就转化为“前i−1件物品放入剩下的容量为v−C i的背包中”，此时能获得的最大价值就是F[i−1,v−C i]再加上通过放入第i件物品获得的价值W i。
伪代码如下：F[0,0..V]=0for i=1to Nfor v=C i to VF[i,v]=max{F[i−1,v],F[i−1,v−C i]+W i}1.3优化空间复杂度以上方法的时间和空间复杂度均为O(V N)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O(V)。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组F[i,0..V]的所有值。
那么，如果只用一个数组F[0..V]，能不能保证第i次循环结束后F[v]中表示的就是我们定义的状态F[i,v]呢？F[i,v]是由F[i−1,v]和F[i−1,v−C i]两个子问题递推而来，能否保证在推F[i,v]时（也即在第i次主循环中推F[v]时）能够取用F[i−1,v]和F[i−1,v−C i]的值呢？事实上，这要求在每次主循环中我们以v=V..0的递减顺序计算F[v]，这样才能保证推F[v]时F[v−C i]保存的是状态F[i−1,v−C i]的值。
伪代码如下：F[0..V]=0for i=1to Nfor v=V to C iF[v]=max{F[v],F[v−C i]+W i}其中的F[v]=max{F[v],F[v−C i]+W i}一句，恰就对应于我们原来的转移方程，因为现在的F[v−C i]就相当于原来的F[i−1,v−C i]。
如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了F[i,v]由F[i,v−C i]推导得到，与本题意不符。
事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。
def ZeroOnePack(F,C,W)for v=V to CF[v]=max(F[v],f[v−C]+W)有了这个过程以后，01背包问题的伪代码就可以这样写：for i=1to NZeroOnePack(F,C i,W i)1.4初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。
有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。
一种区别这两种问法的实现方法是在初始化的时候有所不同。
3如果是第一种问法，要求恰好装满背包，那么在初始化时除了F[0]为0，其它F[1..V]均设为−∞，这样就可以保证最终得到的F[V]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将F[0..V]全部设为0。
这是为什么呢？可以这样理解：初始化的F数组事实上就是在没有任何物品可以放入背包时的合法状态。
如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为-∞了。
如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。
这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。
1.5一个常数优化上面伪代码中的for i=1to Nfor v=V to C i中第二重循环的下限可以改进。
它可以被优化为for i=1to NW i,C i)for v=V to max(V−ΣNi这个优化之所以成立的原因请读者自己思考。
（提示：使用二维的转移方程思考较易。
）1.6小结01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想。
另外，别的类型的背包问题往往也可以转换成01背包问题求解。
故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及空间复杂度怎样被优化。
2完全背包问题2.1题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。
放入第i种物品的耗费的空间是C i，得到的价值是W i。
求解：将哪些物品装入背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
2.2基本思路这个问题非常类似于01背包问题，所不同的是每种物品有无限件。
也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……直至取⌊V/C i⌋件等很多种。
4如果仍然按照解01背包时的思路，令F[i,v]表示前i种物品恰放入一个容量为v的背包的最大权值。
仍然可以按照每种物品不同的策略写出状态转移方程，像这样：F[i,v]=max{F[i−1,v−kC i]+kW i|0≤kC i≤v}这跟01背包问题一样有O(V N)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态F[i,v]的时间是O(vC i)，总的复杂度可以认为是O(NVΣVC i)，是比较大的。
将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。
这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。
但我们还是要试图改进这个复杂度。
2.3一个简单有效的优化完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足C i≤C j且W i≥W j，则将可以将物品j直接去掉，不用考虑。
这个优化的正确性是显然的：任何情况下都可将价值小耗费高的j换成物美价廉的i，得到的方案至少不会更差。
对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。
然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。
这个优化可以简单的O(N2)地实现，一般都可以承受。
另外，针对背包问题而言，比较不错的一种方法是：首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O(V+N)地完成这个优化。
这个不太重要的过程就不给出伪代码了，希望你能独立思考写出伪代码或程序。
2.4转化为01背包问题求解01背包问题是最基本的背包问题，我们可以考虑把完全背包问题转化为01背包问题来解。
最简单的想法是，考虑到第i种物品最多选⌊VC i⌋件，于是可以把第i种物品转化为⌊VC i⌋件费用及价值均不变的物品，然后求解这个01背包问题。
这样的做法完全没有改进时间复杂度，但这种方法也指明了将完全背包问题转化为01背包问题的思路：将一种物品拆成多件只能选0件或1件的01背包中的物品。
更高效的转化方法是：把第i种物品拆成费用为C i2k、价值为W i2k的若干件物品，其中k取遍满足C i2k≤V的非负整数。
这是二进制的思想。
因为，不管最优策略选几件第i种物品，其件数写成二进制后，总可以表示成若干个2k件物品的和。
这样一来就把每种物品拆成O(log VC i)件物品，是一个很大的改进。
2.5O(V N)的算法这个算法使用一维数组，先看伪代码：F[0..V]=0for i=1to Nfor v=C i to VF[v]=max(F[v],F[v−C i]+W i)5你会发现，这个伪代码与01背包问题的伪代码只有v的循环次序不同而已。
为什么这个算法就可行呢？首先想想为什么01背包中要按照v递减的次序来循环。
让v递减是为了保证第i次循环中的状态F[i,v]是由状态F[i−1,v−C i]递推而来。
换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果F[i−1,v−C i]。
