背包九讲

背包九讲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]]的值。

计算机学习相关书籍大学计算机专业使用的教材可以根据不同学校和课程有所不同，下面是楼主收集的一些经典（大部分是国外）的计算机专业教材：------C++------1.C++ Primer Plus C++ Primer习题集第5版,（美）李普曼,2.P520 C++ Primer（第5版）带书签高清完整版3.C++ Templates4.C++大学教程5.C++对象模型6.C++并发编程实战7.C++标准程序库—自修教程与参考手册8.C++沉思录中文第2版9.C++程序设计语言10.C++编程思想（两卷合订本）11.C++编程规范-101条规则准则与最佳实践12.C++编程调试秘笈13.C++设计新思维-泛型编程与设计之应用14.C++语言的设计和演化15.Effective C++ 中文版第三版高清PDF16.Effective STL中文版17.Modern C++ Design More18.Exceptional C++中文版19.STL源码20.STL源码剖析高清版(剖析+源码)21.提高C++性能的编程技术22.泛型编程与STL中文版23.深入理解C++1124.跟我一起写makefile------Go语言------1.Go并发编程实战2.Go语言圣经3.Go语言学习笔记4.Go语言实战5.Go语言标准库参考6.Go语言程序设计7.Go语言编程8.学习Go 语言(Golang)------Java------1.Head First Java 中文高清版2.Head First Servlet and JSP(高清中文版)3.java从入门到精通（第4版）4.JAVA并发编程实践5.Java性能优化权威指南6.Java核心技术卷1基础知识原书第10版7.Java核心技术卷2高级特性原书第10版8.大话java性能优化9.深入分析JavaWeb技术内幕10.深入剖析Tomcat 深入理解Java虚拟机：JVM高级特性与最佳实践（最新第二版）11.阿里巴巴Java开发手册--1------Java大数据------1.Apache Kafka实战2.Apache Spark源码剖析3.Apache+Kylin权威指南4.Elasticsearch集成Hadoop最佳实践5.Flink基础教程6.Flume构建高可用、可扩展的海量日志采集系统7.Hadoop应用架构8.HBase实战中文版9.Hive编程指南10.Kafka源码解析与实战11.Mahout算法解析与案例实战12.MapReduce设计模式[（美）迈纳，（美）舒克著]13.Scala编程中文版(33章全)14.Spark内核设计的艺术架构设计与实现（耿嘉安）15.Spark大数据分析核心概念技术及实践OCR16.Spark大数据处理：技术、应用与性能优化(全)17.Spark快速大数据分析18.Spark快速数据处理19.Spark机器学习20.Storm技术内幕与大数据实践21.图解Spark -核心技术与案例实战22.大数据Spark企业级实战版23.大数据架构师指南24.实战Elasticsearch、Logstash、Kibana：分布式大数据搜索与日志挖掘及可视25.机器学习与数据挖掘方法和应用（经典）26.深入理解Spark：核心思想与源码分析------Linux------1.Linux 内核设计与实现2.Linux内核设计与实现第3版_优先看3.Linux多线程服务端编程书签高清非扫描-陈硕4.linux常用命令大全Linux环境编程：从应用到内核5.Linux高性能服务器编程6.Linux高级程序设计中文第三版杨宗德--人电出版社7.UNIX 环境高级编程第3版8.Unix-Linux编程实践教程9.UNIX编程艺术-中文版【The+Art+of+UNIX+Programming】10.UNIX网络编程卷1 API UNIX网络编程卷2：进程间通信11.深入Linux内核架构(图灵程序设计丛书·LinuxUNIX系列)12.深入理解Linux内核13.鸟哥的Linux私房菜基础篇和服务器篇------python------1.Head_First_Python（中文版）2.Python Cookbook（第3版）中文版3.Python3程序开发指南Python参考手册(第4版)4.Python学习手册(第4版)5.Python开发技术详解6.Python核心编程第3版中文版7.Python正则表达式-深入浅出8.Python灰帽子——黑客与逆向工程师的Python编程之道9.Python编程入门经典10.Python编程初学者指南11.Python编程快速上手让繁琐工作自动化12.python编程金典13.Python高级编程14.编程小白的第一本python入门书------python数据分析和数据挖掘------1.Python数据分析基础2.Python数据挖掘入门与实践3.Python金融大数据分析4.Tableau：数据可视化之极速BI5.利用python进行数据分析6.数据可视化之美7.数据挖掘原理与算法8.数据挖掘导论-完整版9.用Python写网络爬虫10.精通Scrapy网络爬虫-刘硕------操作系统------pilers_ Principles, Techniques, and Toolsputer Systems_ A Programmer's Perspective3.分布式系统概念与设计原书第5版4.操作系统之哲学原理第2版5.操作系统概念-英文版6.操作系统概念7.操作系统概述-公众号资源8.操作系统真象还原9.操作系统精髓与设计原理第8版10.操作系统精髓与设计原理第9版11.操作系统设计与实现12.深入理解计算机系统第3版13.现代操作系统-英文版14.现代操作系统（第三版）中文版15.编译原理16.自己动手写操作系统17.计算机系统要素-从零开始构建现代计算机-----数据结构与算法------1.C++数据结构与算法（第4版）带书签目录完整版2.JavaScrit数据结构与算法（第2版）3.Java数据结构和算法4.严蔚敏：数据结构题集(C语言版)5.分布式算法导论6.剑指offer7.啊哈！算法哈磊8.大话数据结构9.妙趣横生的算法（C语言实现第2版）10.挑战程序设计竞赛(第2版)11.数据结构C语言严蔚敏pdf12.数据结构与算法Python语言描述_裘宗燕13.数据结构与算法分析C++描述14.数据结构与算法分析——Java语言描述15.数据结构与算法分析：C语言描述原书第2版高清版16.漫画算法：小灰的算法之旅17.程序员代码面试指南IT名企算法与数据结构题目最优解（左程云著）18.程序员的算法趣题19.算法(第4版)20.算法之道21.算法分析与设计22.算法图解23.算法竞赛入门经典训练指南24.算法谜题25.编程之美-完整版26.编程珠玑第二版人民邮电出版社27.背包九讲28.谷歌大佬总结的Leetcode刷题笔记，支持Java、C++、Go三种语言29.趣学算法------校招和面经------1.C++牛客大佬总结面试经验2.c++面经总结3.Java程序员面试宝典4.Java突击面试总结5.Java面试突击-V36.招聘笔记7.机器学习8.算法工程师带你去面试9.机器学习常见面试题10.牛客SQL练习题1-61答案与解析11.牛客网IT名企2016笔试真题+答案12.牛客网Java工程师校招面试题库13.程序员面试宝典14.阿里Java面试问题大全------计算机网络------puter Networking_ A Top-down Approachputer Networks, A Systems Approach3.HTTP权威指南4.Http核心总结5.TCP-IP详解卷1：协议原书第2版6.TCP-IP详解卷三7.TCP-IP详解卷二：实现8.tcp源码分析9.Wireshark 数据包分析实战（第二版）10.Wireshark网络分析就这么简单11.Wireshark网络分析的艺术12.图解HTTP13.图解TCPIP(第5版)14.网络是怎样连接的(图灵程序设计丛书)15.计算机网络第七版16.计算机网络-自顶向下方法-第6版17.计算机网络：系统方法18.计算机网络。

下面总结一些小小的经验：1、组队很重要，队友们一定要能谈得来（曾经发生一组队员互相不服气，结果各自做各的，成绩就可想而知了），除此之外，队员之间一定要各有所常，建模嘛，无非就是查阅文献，建立模型，分析数据，编程，写文章，较对等等，保证你们组每个人都会有一些强项，当然男女生也应该都是要有的，所谓男女搭配，干活不累，嘿嘿;2、文章整洁很重要。

如果你是评委的话，肯定喜欢写的文章有条理，图文并茂之类的文章，将心比心，抓住评委的心才是最重要。

3、做建模创新很重要。

这么多的文章你的要想脱颖而出，创新也必须的，当然，你可以想你这篇文章结合了什么什么方法，最好把那方法说得天花乱坠，但不可华而不实，这就行啦。

4、摘要很重要。

以前大学生比赛的时候，是先通过摘要就刷一批，我觉得这是很公平的方法，摘要就是说明你这篇文章的特色和结构的，如果摘要我都不愿意看，干嘛花时间看你的正文。

5、人品很重要，还是我那句话，莫要太看重结果，抱着神马都是浮云的心态~~~数模经历入门篇平时有不少人会加我QQ，然后问诸如“什么是数模”“我该怎么学数模”之类的问题。

这里不是不鼓励大家和我讨论，而是有些问题google或baidu一下很容易得到答案，完全没有必要去问学长或老师。

而且使用搜索引擎的能力在数学建模中也是一个非常重要的能力。

这里推荐一些书，建议刚接触数学建模的朋友们看姜启源、谢金星的《数学模型》，这本书比较全面地介绍了数学建模中一些基本的、常用的模型和方法，有很多的例子，可以全面地了解什么是数学模型，也能基本地掌握如何抽象建模等。

希望进一步深入的同学推荐姜启源、谢金星的《数学模型案例集》，这本书里有不少比较有意思的问题，可以尝试自己做一下，难度比正式比赛要差很多，但是对于初学者来说比较容易上手。

也推荐叶其孝的那套黑书，虽然内容有点老，但是有很多比较有意思的解题思路等。

这里推荐一个很不错的数学建模网站：，那里有很多非常不错的学习资料。

对于那些已经有一些数学建模基础的同学则不推荐读叶其孝的那套书，而是可以直接在网上找一些往年国一或是美赛特等的文章，仔细阅读，了解其中的方法，然后自己动手重新做一遍。

ACM暑期集训报告院系：专业：年级：学号：姓名：日期：西南交通大学目录目录.................................................. 错误!未定义书签。

第1章动态计划（dp） ............................ 错误!未定义书签。

简介.................................................... 错误!未定义书签。

教师内容................................................ 错误!未定义书签。

大体dp——背包问题..................................... 错误!未定义书签。

假设干经典dp及常见优化.................................. 错误!未定义书签。

类似题目................................................. 错误!未定义书签。

参考文献........................................... 错误!未定义书签。

附录1 暑期集训心得体会............................. 错误!未定义书签。

第1章动态计划（dp）（题目采纳2号黑体居中，下空1行）简介（题目采纳四号黑体，正文内容采纳小四号字体，倍行距）在解决问题的时候咱们常常碰到这种问题：在多种方式的操作下咱们如何取得一个最优的方式让咱们取得中意的结果。

这时咱们大多人的思想确实是贪婪。

不错贪婪确实是一个不错的算法，第一他简单容易想到，咱们在操作起来也比较容易。

此刻我推荐几道咱们oj上的贪婪算法的题：soj1562药品运输 soj1585 Climbing mountain。

为了引入动归算法我先拿药品运输这道题简单说一下贪婪算法。

例如1：药品运输（题目采纳小四号Times New Roman字体）Description大地震后，某灾区急需一批药品，此刻有N种药品需要运往灾区，而咱们的运输能力有限，此刻仅有M辆运输车用来运输这批药品，已知不同的药品对灾区具有不同的作用（“作用”用一个整数表示其大小），不同的药品需要的运输力（必要的车辆运载力）不同，而不同的车辆也具有不同的运输力。

背包问题之零⼀背包注:参考⽂献《背包九讲》.零⼀背包问题⼀:题⽬描述 有 N 件物品和⼀个容量为 V 的背包.放⼊第 i 件物品耗⽤的费⽤为C i(即所占⽤背包的体积),得到的价值是 W i.求将哪些物品装⼊背包所得到的总价值最⼤.⼆:基本思路 01背包是最基础的背包问题,这道题的特点是每种物品仅有⼀件,可以选择放或不放,且不要求背包必须被放满,只要求最后的总价值最⼤. ⽤⼦问题定义状态:F[i][v] 表⽰对于前 i 件物品,当背包容量为 v 时所能得到的价值最⼤值.设想,将 "前 i 件物品放⼊容量为 v 的背包中" 这个⼦问题,若只考虑第 i 件物品的策略(要么放要么不放),那么就可以转化为⼀个之和前 i - 1 件物品相关的问题.如果不放第 i 件物品, 那么问题就转化为 ”前 i - 1 件物品放⼊容量为 v 的背包中“,价值就是 F[i - 1][v]; 如果放第 i 件物品,那么问题就转化为 ”前 i - 1 件物品放⼊剩下的容量为v - C i的背包中”, 此时获得的价值为 F[i - 1][v - C i] + W i。

特殊的，当 v < C i时，可以认为当前的容量是放不下第 i 件物品的，即此时相当于不放第 i 件物品的价值F[i - 1][v].分析到这⾥则可得状态转移⽅程为: F[i][v] = v < C i F[i - 1][v] : max( F[i - 1][v], F[i - 1][v - C i] + W i ).在这⾥要特别的说明⼀下,这个⽅程⾮常重要,⼀定要知道这是怎么推出来的,⼏乎后⾯的所有的背包问题都和这个⽅程有着密不可分的联系.伪代码如下:F[0...N][0...V] <--- 0for i <--- 1 to N for v <--- C i to V F[i][v] = v < C i F[i - 1][v] : max( F[i - 1][v], F[i - 1][v - C i] + W i );具体代码:1void _01Pack(int F[][MAXV], int N, int V, int C[], int W[]){2 memset(F, 0, sizeof(F));3for(int i = 1; i <= N; i++) {4for(int v = 0; v <= V; v++) {5 F[i][v] = v < C[i] ? F[i - 1][v] : max(F[i - 1][v], F[i - 1][v - C[i]] + W[i]); //放或者不放两者之中选择最优者6 }7 }8 }三:优化空间复杂度 可以清楚的看到上⾯算法的时间复杂度和空间复杂度均为 O(N * V), 这⾥时间复杂度已经不能得到优化,但是空间复杂度确可以优化到O(V). 先看上⾯代码是如何实现的.最外⾯⼀层循环,每次计算出⼆维数组 F[i][0...V] 的值,计算的时候 F[i][0...V] 是由它的上⼀层 F[i - 1][0...V] ⽽得到的.那么如果把这个数组换成⼀维的 F[v] 那么还能保留上⼀次的状态吗.答案是可以的.由于动态规划算法的⽆后效性,第 i + 1 件物品的选择与否不会影响到第 i 件物品(即它的前⼀件物品)的选择状态.那么可以在上⾯第⼆次循环中按照 v <--- V...0 递减的顺序来计算 F[v], 这样计算F[v] 时所需要的状态 F[v] 和 F[v - C i] + W i 仍然还是上⼀次的状态.⽽计算 F[v] 之后, v 的顺序是递减的, F[v] 不会影响到 F[v'] (v' < v), 因为F[v']只与 F[v'](上⼀次的值) 和 F[v - C i] 有关, ⽽ F[v] > F[v'] > F[v' - C i]. 所以⼜可得状态转移⽅程. F[v] = max( F[v], F[v - C i] + W i ).伪代码如下:F[0...V] <--- 0for i <--- 1 to N for v <--- V to C i F[v] = max( F[v], F[v - C i] + W i );具体代码:1void _01Pack(int F[], int N, int V, int C[], int W[]){2 memset(F, 0, sizeof(F));3for(int i = 1; i <= N; i++) {4for(int v = V; v >= C[i]; v--) {5 F[i][v] = max(F[v], F[v - C[i]] + W[i]);6 }7 }8 }可以看到从第⼀个状态转移⽅程到第⼆个状态转移⽅程的空间优化效率还是挺⼤的: F[i][v] = max( F[i - 1][v], F[i - 1][v - C i] + W i ). ----> F[v] = max( F[v], F[v - C i] + W i ).在第⼆个⽅程中 F[v]1 = max(F[v]2, F[v - C i] + W i), 其实 F[v]2 就相当与⽅程⼀中的 F[i - 1][v], 对应的 F[v - C i] + W i就相当于 F[i -1][v - C i] + W i.这⼀正确性是在内层循环递减的前提下才成⽴的.否则, 将内层循环改为递增, 那么 F[i][v] 其实是由 F[i][v] 和 F[i][v - C i] 推出来的,这不符合基本思路中的探讨.之前说过由于 01背包的特殊性,这⾥将 01背包抽象化,⽅便之后的调⽤.解决单个物品 01背包的伪代码:def ZeroOnePack (F, C, W) for v <--- V to C F[v] = max( F[v], F[v - C] + W );这么写之后, 01背包总问题解决的伪代码就可以改写成:F[0...V] <--- 0for i <--- 1 to N ZeroOnePack(F, C[i], W[i]);具体代码:1const int MAXN = 10000;2int N, V, C[MAXN], W[MAXN];34void ZeroOnePack(int F[], int C, int W) { // 对于单个物品的决策5for(int v = V; v >= C; v--) {6 F[v] = max(F[v], F[v- C] + W);7 }8 }910void solv(int F[]) {11 memset(F, 0, sizeof(F));12for(int i = 1; i <= V; i++) {13 ZeroOnePack(F, C[i], W[i]);14 }15 }四: 01背包问题的拓展 ------ 初始化的细节问题 在上述 01背包的问题中,仅问得是 “如何选取,才能使的最后的总价值最⼤”, 这⾥并没有规定是否必须装满背包, 但是有的题将会给予这个附加条件, 即“在要求恰好装满背包的前提下, 如何选取物品, 才能使的最后的总价值最⼤ ”. 这两种问法, 在代码实现上相差⽆⼏.如果是上述问法,要求 “恰好装满背包”, 那么在初始化时除了将 F[0] 赋值为 0 之外, 其他的 F[1...V] 都应该赋值为 -∞,这样就可以保证最后的得到的 F[V] 是⼀种恰好装满背包的最优解.如果没有要求必须把背包装满,⽽是只希望价值尽量最⼤,初始化时应该将F[0...V] 全部设置为 0. 之所以可以这么做,是因为初始化的 F[] 事实就是没有任何物品放⼊背包时的合法状态.如果要求背包恰好装满,那么只有容量为 0 的背包在什么也不装且价值为 0 的情况下被装 "恰好装满",其他容量的背包如果不装物品, 那么默认的情况下都是不合法状态,应该被赋值为 -∞, 即对于第⼀个物品⽽⾔, 其合法状态只能由 F[0] 转移得到.如果背包并⾮必须被装满,那么任何容量的背包在没有物品可装时都存在⼀个合法解,即什么都不装,且这个解的价值为 0.所以将其全部初始化为 0 是可以的. 注:这个技巧完全可以拓展到其他背包问题中.伪代码:def ZeroOnePack (F, C, W) for v <--- V to C F[v] = max( F[v], F[v - C] + W )end defdef slov() F[0] = 0, F[1...V] <--- -∞ for i <--- 1 to N ZeroOnePack(F, C[i], W[i])end def具体代码:1const int MAXN = 10000;2int N, V, C[MAXN], W[MAXN];34void ZeroOnePack(int F[], int C, int W) {5for(int v = V; v >= C; v--) {6 F[v] = max(F[v], F[v- C] + W);7 }8 }910void solv(int F[]) {11 F[0] = 0;12for(int i = 1; i <= V; i++) F[i] = INT_MIN; // 除F[0] = 0之外, 其他全部赋值为负⽆穷13for(int i = 1; i <= V; i++) {14 ZeroOnePack(F, C[i], W[i]);15 }16 }五:⼀个常数级别的优化上述伪代码的:for i <--- 1 to N for v <--- V to C i可以优化为:for i <--- 1 to N for v <--- V to max( V - SUM(i...N)C i, C i)。

1.你让工人为你工作7天，回报是一根金条，这个金条平分成相连的7段，每天结束的时候,工人会向你要一段金条。

如果只允许你两次把金条弄断，你如何给你的工人付费？2.有1000个苹果，将它们放在100个箱子里，怎么放才能让我向你要苹果的时候，你都能整箱整箱的给我,你的给法是否唯一?这两个题目我想很多人都曾做过，如果你会做第一个题目，那你也应该会做第二个...如果不会,请看文章标题的提示...下面就个人理解给出这种二进制的思想:我第一次看到的是第二个题目，一开始，没什么思路，只是一步步的试，比如说，如果要一个苹果，我就必须要有一个箱子里放1个苹果，这是没法改的，如果要两个苹果，我要么是给一个放有2个苹果的箱子，要么是给两个各放有1个苹果的箱子，显然后面那种不行，因为当向我们要三个苹果的时候，我们至少要用掉三个箱子...后来突然想到高中涂高考志愿卡时,遇到的一个有趣的1248码,卡片只给出四个涂色框,第一个表示1第二个表示2,第三个表示4,第四个表示8,如果我们的号码中有个数字是7,我们就将1 2 4都涂上.很好,由1,2,4,8这几个数字,我们可以看出,它们能组成1-15中的任何一个数字,如果我们就用这种方法,用掉4个箱子,那第五个箱子,我们就必须要放16个苹果,这样一来,可以组成1-31中的任何一个数字,第六个箱子我们得放32个...依此类推,我们放的是1,2,4,8,16,32...惊讶的发现:这组数字的规律是一个以2为比的等比递增数列,自然而然想到二进制化十进制的方法,11111111B=2的7次幂+2的6次幂+2的5次幂+2的4次幂+... 如此一来,如果我们让每个箱子各对应一个具有10bit的二进制的一位,1表示在第n个箱子放2的n次幂个苹果,我们可以算出,0000000000B~1111111111B的表数范围为:0-1023,而且可以看出,每一个在这中间的数都可以唯一的对应一个二进制数,也就是说针对不同数目的苹果,我们给箱子的时候,只有一种给法,因为只有1000个苹果,所以最后一个箱子我们没有放512个苹果,而是只放了489个,那么1-488只有唯一的给法,489-1000有两种给法.(更正一下:只有489-511有两种给法...1-488和512-1000都只有唯一的给法...)显然,第一个题目也是用到了这种思想,我们可以将金条分成1、2、4三段,不管哪天工人向我们要金条,我们都能给他,比如说:工人第一天没有要金条,第二天要的时候,我们给他2段,第三天他没有要,第四天他要我们给金条,于是我们将那块四段的给他,收回那个2段的...二进制思想和多重背包问题二进制思想问题描述：假设有1000个苹果，现在要取n个苹果，如何取？正常的做法应该是将苹果一个一个拿出来，直到n个苹果被取出来。

不撞南墙不回头——树规总结焦作一中信息学oy之所以这样命名树规，是因为树规的这一特殊性：没有环，dfs是不会重复，而且具有明显而又严格的层数关系。

利用这一特性，我们可以很清晰地根据题目写出一个在树（型结构）上的记忆化搜索的程序。

而深搜的特点，就是“不撞南墙不回头”。

这一点在之后的文章中会详细的介绍。

首先是扫盲，介绍几条名词的专业解释以显示我的高端（大部分人可以略过，因为学习到树规的人一下应该都懂……）：动态规划：问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。

要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。

动态规划就是解决多阶段决策最优化问题的一种思想方法。

阶段：将所给问题的过程，按时间或空间（树归中是空间，即层数）特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。

状态：各阶段开始时的客观条件叫做状态。

决策：当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。

（即孩子节点和父亲节点的关系）策略：由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。

状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由k阶段到k+1阶段（在树中是孩子节点和父亲节点）状态的演变规律，称为状态转移方程。

目标函数与最优化概念：目标函数是衡量多阶段决策过程优劣的准则。

最优化概念是在一定条件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。

树的特点与性质：1、有n个点，n-1条边的无向图，任意两顶点间可达2、无向图中任意两个点间有且只有一条路3、一个点至多有一个前趋，但可以有多个后继4、无向图中没有环；废话说完了，下面是正文：拿到一道树规题，我们有以下3个步骤需要执行：1.判断是否是一道树规题：即判断数据结构是否是一棵树，然后是否符合动态规划的要求。

acm学习计划篇一：ACM学习计划ACM学习计划正在学（learning），未学（waiting），已学（cut vovering）初期:一.基本算法:(1)枚举. (poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:(1)图的深度优先遍历和广度优先遍历.(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240,po j1511,poj1847,poj2387,poj3268,poj3037,poj1502,poj1797,poj3615,poj3660,poj 3013,poj3159,poj1275)(3)最小生成树算法(prim,kruskal)(poj1789,poj2485,poj1258,poj3026,poj1861,poj2395,po j2377,poj2421,poj1679,poj1751,poj1354,poj1251,poj36 25,poj3522)(4)拓扑排序 (poj1094)(5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020,poj1274,poj3692,poj2195,poj1466,poj1469,poj2239,poj1325,poj2771,poj 1422,poj2594,poj1087)(6)最大流的增广路算法(EK算法,SAP算法,Dinic算法).(poj1459,poj3436,poj1273,poj3281,poj1087,poj1149 ,p oj1698,poj2195,poj1815)三.数据结构.(1)串 (poj1035,poj3080,poj1936)(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)(3)简单并查集的应用. (poj1182,poj1456,poj1611,poj1988,poj2524,poj2236)(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)(poj3349,poj3274,POJ2151,poj1840,pojXX,poj2503)(5)哈夫曼树(poj3253)(6)堆(7)trie树(静态建树、动态建树) (poj2513poj3630,poj1204,poj1056,hduoj1251,hduoj1247)四.简单搜索(1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251)(2)广度优先搜索(poj3278,poj1426,poj3126,)(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)五.动态规划(1)背包问题. (poj1837,poj1276)(2)型如下表的简单DP(可参考lrj的书 page149):[j]=opt{D[i]+w(i,j)} (poj3267,poj1836,poj1260,poj2533)[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)(poj3176,poj1080,poj1159)[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)六.数学(1)组合数学:1.加法原理和乘法原理.2.排列组合.3.递推关系.(POJ3252,poj1850,poj1019,poj1942)(2)数论.1.素数与整除问题2.进制位.3.同余模运算.(poj2635, poj3292,poj1845,poj2115)(3)计算方法.1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)七.计算几何学.(1)几何公式.(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等).(poj2031,poj1039)(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交) (poj1408,poj1584)(4)凸包. (poj2187,poj1113,poj1228,poj1794,pojXX,hoj1392,hoj1 348, hoj2202,hoj2215)中级:一.基本算法:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)二.图算法:(1)差分约束系统的建立和求解. (poj1201,poj2983,poj1364,poj3169,poj3159 ,poj1716,poj1275,zoj1260,zoj1420,zoj1455) (利用最短路Bellman_Ford和SPFA算法）。

0-1背包问题的四种写法本节回顾0-1背包的基本模型，关于它的实现有很多种写法，这⾥对不同实现做个简单列举，主要是写代码练⼿了，主要有以下⼏⽅⾯内容：==0-1背包问题定义 & 基本实现==0-1背包使⽤滚动数组压缩空间==0-1背包使⽤⼀维数组==0-1背包恰好背满==0-1背包输出最优⽅案========================================0-1背包问题定义 & 基本实现问题：有个容量为V⼤⼩的背包，有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的物品，每种物品只有⼀个，想计算⼀下最多能放多少价值的货物。

DP的关键也是难点是找到最优⼦结构和重叠⼦问题，进⽽找到状态转移⽅程，编码就相对容易些。

最优⼦结构保证每个状态是最优的，重叠⼦问题也即n状态的求法和n-1状态的求法是⼀样的；DP在实现上⼀般是根据状态转移⽅程⾃底向上的迭代求得最优解（也可以使⽤递归⾃顶向下求解）。

回到0-1背包，每个物体i，对应着两种状态：放⼊&不放⼊背包。

背包的最优解是在⾯对每个物体时选择能够最⼤化背包价值的状态。

0-1背包的状态转移⽅程为f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }f(i,v)表⽰前i个物体⾯对容量为v时背包的最⼤价值，c[i]代表物体i的cost(即重量)，w[i]代表物体i的价值；如果第i个物体不放⼊背包，则背包的最⼤价值等于前i-1个物体⾯对容量v的最⼤价值；如果第i个物体选择放⼊，则背包的最⼤价值等于前i-1个物体⾯对容量v-cost[i]的最⼤价值加上物体i的价值w[i]。

对于实现，⼀般采⽤⼀个⼆维数组（状态转移矩阵）dp[i][j]来记录各个⼦问题的最优状态，其中dp[i][j]表⽰前i个物体⾯对容量j背包的最⼤价值。

下⾯给出0-1背包的基本实现，时间复杂度为O(N*V)，空间复杂度也为O(N*V)，初始化的合法状态很重要，对于第⼀个物体即f[0][j]，如果容量j⼩于第⼀个物体（编号为0）的重量，则背包的最⼤价值为0，如果容量j⼤于第⼀个物体的重量，则背包最⼤价值便为该物体的价值。

背包问题九讲目录第一讲 01背包问题第二讲完全背包问题第三讲多重背包问题第四讲混合三种背包问题第五讲二维费用的背包问题第六讲分组的背包问题第七讲有依赖的背包问题第八讲泛化物品第九讲背包问题问法的变化附：USACO中的背包问题前言本篇文章是我(dd_engi)正在进行中的一个雄心勃勃的写作计划的一部分，这个计划的内容是写作一份较为完善的NOIP难度的动态规划总结，名为《解动态规划题的基本思考方式》。

现在你看到的是这个写作计划最先发布的一部分。

背包问题是一个经典的动态规划模型。

它既简单形象容易理解，又在某种程度上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例题，我也将它放在我的写作计划的第一部分。

读本文最重要的是思考。

因为我的语言和写作方式向来不以易于理解为长，思路也偶有跳跃的地方，后面更有需要大量思考才能理解的比较抽象的内容。

更重要的是：不大量思考，绝对不可能学好动态规划这一信息学奥赛中最精致的部分。

你现在看到的是本文的1.0正式版。

我会长期维护这份文本，把大家的意见和建议融入其中，也会不断加入我在OI学习以及将来可能的ACM-ICPC的征程中得到的新的心得。

但目前本文还没有一个固定的发布页面，想了解本文是否有更新版本发布，可以在OIBH论坛中以“背包问题九讲”为关键字搜索贴子，每次比较重大的版本更新都会在这里发贴公布。

目录第一讲 01背包问题这是最基本的背包问题，每个物品最多只能放一次。

第二讲完全背包问题第二个基本的背包问题模型，每种物品可以放无限多次。

第三讲多重背包问题每种物品有一个固定的次数上限。

第四讲混合三种背包问题将前面三种简单的问题叠加成较复杂的问题。

第五讲二维费用的背包问题一个简单的常见扩展。

第六讲分组的背包问题一种题目类型，也是一个有用的模型。

后两节的基础。

第七讲有依赖的背包问题另一种给物品的选取加上限制的方法。

第八讲泛化物品我自己关于背包问题的思考成果，有一点抽象。

背包问题----完全背包（最优⽅案总数分析及实现）本⼈博⽂》中已详细谈过完全背包问题，同时在博⽂》中也总结过01背包的最优⽅案总数的实现。

这⾥我们模仿01背包最优⽅案总数⽅法给出完全背包的最优⽅案求解⽅法。

重写完全背包的动态规划的状态及状态⽅程：完全背包是在N种物品中选取若⼲件（同⼀种物品可多次选取）放在空间为V的背包⾥，每种物品的体积为C1，C2，…，C n，与之相对应的价值为W1,W2，…，W n.求解怎么装物品可使背包⾥物品总价值最⼤。

设物品种类为N，背包容量为V，每种物品的体积为C[i]，价值为W[i]。

⼦问题定义：F[i][j]表⽰前i种物品中选取若⼲件物品放⼊剩余空间为j的背包中所能得到的最⼤价值。

状态⽅程为：(2-2)在⽂章》中曾定义G[i][j]代表F[i][j]的⽅案总数。

这⾥我们也做相同的定义，那么最终的结果应该为G[N][V]。

由01背包转变到完全背包后G[i][j]该怎么求？对于01背包来说，G[i][j]求法如下（摘⾃：》）：如果F[i][j]=F[i-1][j]且F[i][j]!=F[i-1][j-C[i]]+W[i]说明在状态[i][j]时只有前i-1件物品的放⼊才会使价值最⼤，所以第i件物品不放⼊，那么到状态[i][j]的⽅案数应该等于[i-1][j]状态的⽅案数即G[i][j]=G[i-1][j]；如果F[i][j]=F[i-1][j-C[i]]+W[i] 且F[i][j]!=F[i-1][j]说明在状态[i][j]时只有第i件物品的加⼊才会使总价值最⼤，那么⽅案数应该等于[i-1][j-C[i]]的⽅案数，即G[i] [j]=G[i-1][j-C[i]]；如果F[i][j]=F[i-1][j-C[i]]+W[i] 且F[i][j]=F[i-1][j]则说明即可以通过状态[i-1][j]在不加⼊第i件物品情况下到达状态[i][j]，⼜可以通过状态[i-1][j-C[i]]在加⼊第i件物品的情况下到达状态[i][j]，并且这两种情况都使得价值最⼤且这两种情况是互斥的，所以⽅案总数为G[i][j]=G[i-1][j-C[i]]+ G[i-1][j]。