后续还会不断更新数据和大家关注的问题 (已更新24拟招名额-在第五个模块数据统计里)下一次更新时间：2024年10月更新保研数据重要通知：2022年7月15号，计算机专硕从数二英二改为数一英一文章很长，但是包含了所有基本问题，没有耐心的可以根据目录跳到感兴趣的模块，没写到的问题可以评论区留言，看到会解答。一、 北科基本情况介绍+计算机择校建议1 . 北科基本情况：1）北京科技大学-211-北四环-计算机学科评估B+2）北科收计算机专业研究生的有五个学院(23年新增人工智能研究院)：计算机与通信工程学院、顺德研究生院、国家材料服役安全科学中心、钢铁共性技术协同创新中心、人工智能研究院。（具体情况在第四部分）。3）目前初试专业课还是自命题871计算机基础综合一（包含数据结构、计算机组成原理），复试笔试549计算机基础综合二（包含 操作系统、计算机体系结构、软件工程），复试有机试。4）北科无歧视，保护一志愿。本人普通双非上岸，可以放心报考。5）北科会公布保研人数，实际招生人数和报考人数。初试公布排名，信息非常透明，让人能够很清楚的了解情况。这一点非常Nice！！！因为据我经验，有些学校是不公布排名的，所以对边缘考生不太友好2. 计算机择校建议：计算机越来越卷，而第一步择校会成为你一整年努力的一个目标，处于一个非常重要的状态。很多人都说考得好不如选得好，那如何确定自己想考哪一个学校，这里说一下自己的一些看法吧（仅供参考哈）核心就是要结合你以后的发展和自己的实力共同考虑如果你以后从事计算机行业，梦想去往大城市打拼出一番成就。那就搏一搏北上广深的985和211，需要综合专业课初试内容+历年分数线+报录比+复试情况+复试比这些情况，结合你的水平来做选择。如果你只是单纯想读个研究生丰富一下自己的学历，以后可能也未必从事计算机方面工作，希望可以容易上岸，就可以考虑非热门城市的学校，虽然可能报考人数也很多（计算机没有不卷的），但是竞争会稍微小一点。如果你想去大城市，但是觉得自己实力可能不太够，又希望一战上岸，可以看看大城市里计算机学科评估不太强的学校，或者是计算机并不是强势专业的学校。如果你想去大城市的好学校，但是觉得对自己来说很难，可是有坚定的信念必须要读，二战也值得，那就去冲。PS：官方文件可以顺便看看上年的，了解有没有新增的计算机招生专业或者学院，也是竞争力稍微小一点的选择。3. 常见问题汇总：1）北京压分严重吗问题不大。其实我觉得分数和你真正水平一样（平时对自己就严格要求，你感受不到压分）。这个是相对来说的，因为别的地区看卷子会比北京松一点，所以别的地区公共课就很高。有人说调剂的时候我们的分数不就没有优势。我一战北邮复试被刷，经历过调剂，调剂不看分数(我19年调剂，那年分数也是离奇的高，身边很多400左右的，我只有328也是可以收到北京一个双非一本的录取通知)。调剂看的是你本科，如果你本科985 211 你就有可能调剂到985 211院校。如果你和我一样是双非，调剂到985 211的概率还是很小的。2）我是二本（三本）是不是很难考北科研究生想来就冲。 大家都一样，本科期间学的不错的大部分也就保研了吧，很多人专业课起跑线不是很高，拼的不是你本科，是你的学习能力。如果你能把所有知识点掌握，考高分，那你肯定能上。北科不搞歧视。不会说因为你本科不好，复试特意把你刷掉。只要你分数高，复试不拖后腿，就可以上岸。虽然本科水平代表一定的学习能力，但是只要你坚定的想考，我觉得就可以拼一把。另外，需要知道考研变数很大，有时候你尽力了可能结果不尽人意，这很常见。每个人都需要做好失败的准备。如果你能接受最坏的结果，那你就无所畏惧了，直接冲。如果你求稳，不愿意二战，不愿意失败，那你可能要谨慎选择学校。3）北科歧视跨考吗北科可以说是比较公平公正，信息透明的，没有歧视现象，这个不用担心。不过计算机竞争太大了，你需要多在专业课下功夫，付出比科班学生更多的努力才可以成功上岸。二、2024北科考研时间节点2023年9月出考纲和拟招人数（有变化会提前一两个月出通知）2023年9月底预报名，10月正式报名（预报名和正式报名一样，不用着急）10月底保研结束出保研录取人数2023年12月底初试2024年2月中下旬公布初试成绩（目前也都会公布个人排名）2024年3月初公布国家线2024年3月中下旬公布复试线和名单(历年3.20左右，复试前一周公布复试方案和名单)2024年3月底复试（历年3.26左右复试，北科复试相对来说较晚，纠结一志愿和调剂院校的需要提前考虑）2024年4月中上旬公布拟录取名单(复试结束一周后)三、学硕or 专硕(23考研开始考试科目完全一样，数一英一871)不同点：1）学硕毕业需要小论文+毕业论文，专硕只需要毕业论文就可以了。（但不是硬性要求）2）其实真正毕业的话是看导师是否同意，培养计划文件只是一个参考啦，没有论文有专利也可以毕业，或者是研究生期间一直给老师干项目，有很多工作量证明，也可以毕业。3）专硕统招名额会比学硕多一点其他的没什么不同，不管是培养计划还是研究生期间要做的事情都是无差别的。有很多同学不知道该怎么选。我觉得可以从以后的规划和毕业难度来考虑：如果打算研究生毕业后直接工作的话，可以考虑专硕，一方面是毕业要求相对低一点，认真做不会卡你毕业，另一方面专硕统招名额比学硕也多，在考试科目一样的情况下，感觉专硕上岸的机会也会多一点。如果以后还考虑读博，可以考虑一下学硕，一般比较负责任的老师考虑到学硕的毕业条件，往往会督促你写论文，而申请博士也会更看重你的科研成果。（很多人读研才会发现，不读博是因为自己并不适合搞科研，而不是自己不想读，如果本科没有接触过科研工作，自身缺乏创新能力，建议慎重考虑这个想法）四、北科五大学院情况1. 计算机与通信工程学院
这个是大部分人会报考的、也是招收学生最多的一个学院，报录比最高可达到20：1。相对来说竞争压力比较大。因为在本部，北四环，寸土寸金，实验室空间较小，每个人工位有限，电脑设备大部分是继续用实验室已有的，有钱的实验室会购入新电脑。一些严格的老师可能会要求每天实验室打卡，不允许出去实习。因为计通院老师比较多，每个实验室情况各不相同，需要具体了解的话最好找实验室的学长学姐去了解。2. 国家材料服役安全科学中心
很荣幸认识一个妹子和我聊过国科的情况。国科和钢协每年就收两三个人，网上也不容易找到学长学姐。国科在昌平校区，空间比较大，实验室也比较新，电脑设备也会比本部一些实验室要新。这里相对来说要比计通自由，老师可能不会要求你打卡，可以出去找实习。其实非常适合我第一部分说的第三类人来报考。竞争压力相比计通要小一点。往年都是二战生或者本校生知道这个的多一点，不过22年专硕报名人数来了一个激增，之后国材学院的报录比应该会随着知名度的提升而有所增加。3. 钢铁共性技术协同创新中心这个学院我并没有过多了解，所以很多信息我并不确定，表中就空着了。他和国材一样，老师都不属于计通学院，每年只收两三个人，目前报考这个学院的人依旧很少。4. 顺德研究生院这个学院的老师和计通学院是一样的，研一都是在计通学院培养，研二才去顺德，所以我不太了解和计通有什么本质区别。其实早些年都是计通学院招生完分配一部分去顺德，从20年开始独立招生，老师基本上都是在本部，偶尔会去顺德，所以在顺德相对来说也是自由度比较大，可以出去找实习。5. 人工智能研究院这个学院是22年由自动化学院牵头创立的学院，22年只招收自动化专业的保研生，于23年开启了计算机专业的招生，目前招收人数较少，学硕+专硕总名额在9人，其中保研生拟招收7人，考研生拟招收学硕1人，专硕1人。师资是由自动化和计通学院的老师组成的（自动化的老师居多）。四小院毕业后找工作认可度高吗？之前有同学会担心去其他学院学计算机，毕业之后找工作会不会不承认啊有歧视什么的。刚好最近我也秋招了，说一下自己的结论：学校只是敲门砖！！！找工作更多的是看的是你实习经历、项目经历等，而在学校里基本上是读论文做实验和写论文，需求还是不一样的。所以不要觉得进了北科就一定能找到大厂，这个是要看你的实力和经验。想去大厂就针对性的去学岗位要求的技术，去大厂实习，增加经验，所以你在哪个学院都不会影响你找工作。PS：放了五大院的官网链接，一般复试名单、复试方案和拟录取名单都会在各个院官网进行公布。而初试相关的事情都会在北科大招生网公布。关键时间点记得经常看一下官网。五、 近几年数据统计这里只是简单放了一下招生和报考人数统计，戳下方链接可以看四个学院详细数据分析(除了下方表格外，还增加了各个科目的分数分析)1. 计算机与通信工程学院计通学院每年统招人数比较稳定，学硕基本上是20人左右。专硕之前有40人左右，是因为包含顺德人数在内，自20年顺德独立招生后，计通专硕人数就少了，基本上统招30人左右。不过每年都会扩招几个人。扩招人数见表格“录取数”中的括号里数据。线下复试的复录比是1：1.4，网络复试是1：1.3左右。2. 钢铁共性技术协同创新中心每年招生人数比较稳定，基本上是两三个人。其实只是想收保研生的，可没有人愿意过来，所以基本上所有名额都会给统招，不过报考人数也很少，而且报考的人大部分过不了国家线的，可以观察表格，钢协学硕这两年一志愿都没有过国家线的，所以都是调剂生来面试。钢协专硕情况好一点，而且近几年也不需要调剂生源了。22年随着计算机生源越来越多，钢协的竞争也慢慢开始上涨了。3. 国家材料服役安全科学中心每年招生计划比较稳定，收两三个人。其实本来也是想要保研生源，不过没人来，所以基本上名额都是统考，不过报名人数也比较少，也有很多过不了国家线，最后还是会收调剂来面试。今年我记得有个公众号宣传了一下国科，专硕报考人数突然爆炸了，迎来报考人数的巅峰，之后国材的知名度可能会慢慢上来。4. 顺德研究生院20年开始独立招生，一开始几年只有专硕的，刚开始报名情况呈现出大小年的状况，复试线比计通学院低一点。22年开始收学硕，因为区分了学硕和专硕，所以招生人数劈两半。目前顺德的竞争相比计通来说依旧小一点。5.人工智能研究院人工智能研究院是22年新创立的学院，由自动化学院计划开创的。22年没有计算机相关专业，都是自动化专业，也只招收保研的同学。23年新增加了计算机学硕和专硕，目前计划统招名额都是只有1人，尚不清楚保研会不会占满总人数。六、考纲和考察题型、重难点分布(22年考纲)没用长截图。。。先将就看吧，后期再完善。从20年数据结构换了出题老师，代码题的考察变成了重点，之前数据结构出的很简单，基本上没啥太大参考价值，练手就可以了。（最近几年各个学校都开始改408了，大家也很关注考纲会不会变化，如果有变动会提前通知，一般9月出考纲，有变动应该会在7、8月就发布通知）七、初试用书+初试经验(专业课)关于公共课的备考经验，我有另一篇文章单独写了(点击下面链接)，这里只详细介绍了专业课。1. 初试用书：1）教材：[1]蒋本珊．《计算机组成原理（第3版）》．清华大学出版社，2013[2] 唐朔飞．《计算机组成原理（第2版）》．高等教育出版社，2008[3] 齐悦，夏克俭，姚琳．《数据结构、算法与应用》．清华大学出版社[4] 严蔚敏，吴伟民．《数据结构（C语言版）》．清华大学出版社[1]和[3]是我比较推荐的，对零基础非常友好！[2]和[4]晦涩难懂，大家选一本看就行，不用都看2) 王道计算机考研用书人手一本！入股不亏。3) 专业课真题资料家人们！一定不要激情下单！我当年走过太多坑了，你们一定不要花冤枉钱！看北科考研群里有人二手出机构的真题，就买了，机构卖175，他二手卖130，当时以为我赚了，但是没有最新一年的真题啊！！后来我在网上找到，电子版就要收我50块钱啊！！！还没有人给我答疑，卖了资料就不理人了，不如直接自己新买一本。加了一个QQ群，里面专门卖电子资料，给的目录超级多的东西，电子版只要80块钱还是60块钱，觉得好像很划算啊，还有这么多没见过的资料，结果买来一看真题就是机构真题的电子版，里面的各种笔记根本没有用啊，不仅不全，字迹潦草，而且感觉很老旧，已经不适合现在的需求了。还有很多人的资料卖好几大百，我穷，没买。不过我后来的学生有钱，花了好几大百买了，最后还是来买我的资料了。所以，太贵的资料不要买！(市面上的资料200多的就差不多了)太便宜的资料不要买！(能便宜买都是没成本的，对你价值根本不大)，二手资料如果不够便宜不要买！（不然再找最新一年的真题添添补补花更多钱）市面上资料的答案不够完整，也存在一些错误。因为都是我这样在读研究生写的答案，难免会有错误，如果没有及时整理勘误，做起来很难受。我就把历年真题的答案都整理完，自己出了一本真题集和答案集，也卖了三年了，我带的孩子们反映都不错，中国人不骗中国人！买了我的资料就是我的小贝壳了，从考研到未来读研找工作我都会给你们分享经验Hhhh(我的文章就是不断根据你们的需求进行产出)自己想要宣传但总是被拒绝，所以有时候会觉得买我资料的真的是给了我很多信任资料好评和我的小贝壳双向奔赴hhh买了不好的资料真的会心情不好2. 初试专业课经验(王道+真题就是yyds)第一阶段：暑假之前基础不好的同学要在暑假之前打一下基础，可以看指定教材[1][3]，大概把知识点过一遍第二阶段：暑假7-8月份基础好的暑假开始也不晚。暑假的任务就是把王道的组成原理和数据结构刷完。王道的题目还是比较综合的，有一定的难度，但是如果掌握了，你的基本功会非常牢靠，面对自命题时，也会觉得比较简单。而且北科871经常会出王道原题，所以王道掌握好是非常有用的。第三阶段：9月之后等考纲出了，确认还是871了，就可以去买我的真题资料了hhh。附带全程答疑，不仅答疑真题，王道的题目也可以答疑，性价比我觉得不错，经常有学生因为每天问我题目而培养出大火花..所以我觉得同学们应该是很需要一个高质量答疑的。刷一遍真题能够对北科的出题方向和重点有个大概印象。之后继续二刷王道，因为王道的知识大部分人做不到一步到位，我把王道刷了五遍(因为我二战啦，一年基本上可以三刷)，还是有没有完全掌握的地方，所以知道北科出题重点之后，可以有目标的去二刷、三刷王道。如果可以把王道和真题全部搞懂，融会贯通，考试就问题不大了。常见问题汇总：1）王道里面的题目是不是需要有选择的做会有同学觉得，北科大题占比高，选择题随便看看就行。王道选择题很多，可以重点做大题吗。其实我觉得不可行。王道的大题综合度很高，一般北科是达不到王道的整体难度的。把王道题目掌握了，北科真题对你来说其实很简单。如果你不太关注王道选择，你可能损失很大。因为真题里经常是好多选择来自王道原题的，而且真题的大题一般也不容易得分，不能忽视选择题、填空题的锻炼。专业课复习一定要全面。王道的题目尽量全部掌握，对你专业课的提升会有很大的帮助，不要害怕浪费时间，觉得有捷径可以走。2）王道的题目有点少，其他的书有什么推荐吗如果你基础一般：王道+真题足够。 如果想做别的书，先检查一下自己王道和真题是否真正掌握？记住王道+真题掌握了，是足够应对871的。王道我刷了五遍才真正搞明白，真题刷了两遍才完全落实，根本没有时间去看别的书。基础一般的同学可以不用想这个问题了，觉得题目少，就把它们都搞熟，王道每个题目综合性很强，真题告诉你北科出题的重心。刷题重质不重量，安心复习就好了。如果你基础很厉害，王道+真题很快就全部掌握了。就更没有必要了，可以把时间分给别的科目哈哈哈。3）真题如何高效利用(相同方法也适用于王道做题)核心是认真落实。自己独立解答题目，之后对答案。对答案是关键一步，不仅要看对错，还要真正落实对应知识点。题目作对了，检查是否真正掌握了知识点，如果有猜测成分在，就翻王道/课本对应知识点，重温，并对照题目做好笔记，真正搞懂题目做错答案看懂了，标记出来，翻王道/课本相应知识点，记住自己容易出错的地方，做好笔记，周期性回顾。答案没看懂，标记出来，首先自己尝试找到对应知识点理解答案，实在不懂找学姐答疑，做好笔记（自己原本的思路，哪个点卡住了没思路了，正确思路是怎样），周期性回顾。这样把真题做完一遍，也重温了一遍相关考点，时间会很久，但是落实好了对你大有裨益。 之后二刷。二刷的时候简单题目（完全掌握了）浏览下即可。之前标记好的错题重新做一次，检验是否真正掌握。直到没有做不出来的题目为止，才真正掌握了真题。二刷的时候也可以尝试自己总结自己的心得体会，做某类题目的技巧方法。考前关注你的错题笔记和自己的总结就可以了。4）这个知识点考吗？经常有同学问我某个知识点考不考，因为考纲不是很详细，所以我也不确定某个细小的知识点会不会出。所以我除了串和外设这种大块的没掌握好，还有组原里关于硬件实现的地方没看，其他的小知识点基本上都看了，以防万一。不在考纲肯定不是重点，所以如果学不懂就算了，但是有个印象也是好的。如果时间不够就先不看，如果时间来得及建议大家都过一遍。专业课最重要的就是复习全面，基本功扎实。5）代码如何复习首先根据题目问题，自己想解决方案，把思想中文写出来。然后根据你的想法转换成代码实现，最后对照答案。会存在以下问题无思路 想一会确认没有思路之后，看答案。把答案看懂，思路看明白，再用相似的题目练手。标注出来，以后固定时间回顾一下有思路，代码不会写： 能写多少写多少，卡住了就跳过去写下面的。最后实在不行了，看答案。对照哪里卡住了，标注出来，分析哪里出了问题，应该如何解决，慢慢积累，以后就可以了。有思路，思路和答案不对： 不确定自己想法对不对，可以给我看看。这个思路是很广义的，不是说你和答案一模一样才叫思路和答案一样，比如删除一段数据，你用了覆盖的思想，答案也用了覆盖的思想，这就是思路一样。只不过可能具体语句不同，王道经常会用效率比较好的算法，我们一开始可能只能想到最简单的做法。但是实质上解决问题的思路是一样的有思路，代码写出来了，有很多小错误： 同2需要积累，哪个语法经常用错，记下来，遇见多了就记住了，考前看看代码看不懂，就自己在草稿纸上用手跑一下代码就明白了。写完了代码也是自己在草稿纸上举例子跑一下代码检查哪里有问题八、 复试内容流程和经验1. 复试内容和分数一般在3.20左右会公布复试方案和复试名单。一周后3.26左右进行复试。复试之前要按照复试方案说的进行复试确认、缴费和上传规定文档进行资格审查。23年复试情况线上进行(20年-22年)线下进行(20年之前)复试和初试占比复试250分/初试500分(1:2)复试250分/初试500分(1:2)复试500分/初试500分(1:1)复试内容专业水平(100)：笔试(60)+机试(40)。综合素质(100):面试英语水平(50):面试专业水平(100)：笔试+机试。综合素质(100)：面试。英语水平(50)：面试。专业水平(200)：笔试150+机试50。综合素质(250)：面试。英语水平(50)：面试。复试时间笔试：2h机试：2h面试：15-20min笔试:1.5h； 机试:1.5h ；面试:15-20Min。笔试：3h；机试：3h；面试：15-20min；需要在北科两三天.设备要求机试可用语言：C/C++ java C#。笔试/机试：用windows系统chrome浏览器，双机位，手机开启腾讯会议。机试可用语言：C/C++ java C#。面试：windows/mac均可，用云考场。笔试：一支能写3h的笔。机试：一双熟悉键盘的手。面试：一张能说会道的嘴。注明计通和国科有笔试+机试，钢协、AI院都以面试形式考察。线上目前只有计通和顺德有笔试和机试，钢协和国科只有面试。三个部分必须都要及格才可以线下四大学院的复试方案都是这样1）复试结束一周后公布成绩和拟录取名单。2）而在复试之前接受了其他学校的拟录取通知，视为放弃了复试资格(边缘考生注意选择)3）23年线下复试程序：计通学院安排：3.22日通过北科大研究生报考服务系统进行复试信息确认，并缴纳复试费用、完成心理测评。3.28日上午于机电楼报道3.28日下午14:00-16:00机试，18:00-20:00笔试3.29日-3.30日 面试顺德学院安排：3.22日通过北科大研究生报考服务系统进行复试信息确认，并缴纳复试费用、完成心理测评。3.28日上午于机电楼报道3.28日下午14:00-16:00机试，18:00-20:00笔试3.29日-3.30日 面试国科学院安排：3.23日之前通过北科大研究生报考服务系统进行复试信息确认，并缴纳复试费用、完成心理测评3.24日线上平台报道3.27日上午10:00-12:00面试（在昌平校区面试）3.28日下午14:00-16:00机试，18:00-20:00笔试（在本部和计通一起笔试+机试）钢协学院安排：3.24日上午之前通过北科大研究生报考服务系统进行复试信息确认，并缴纳复试费用、完成心理测评3.28日上午于科技楼报道3.28日 13:30-17:00 面试AI学院安排：3.31日于AI院报道4.1日面试无笔试和机试，面试形式不太一样：专业水平考核分为抽题作答和提问作答两部分，抽题作答共抽5个题目，范围涵盖549三门课《系统结构》、《操作系统》、《软件工程》，考核时间不少于10分钟。综合素质考核以综合面试+PPT展示的形式进行，PPT汇报时间6分钟以内，提问时间不少于6分钟。4） 导师选报
每位学生可填报三名导师，导师会根据学生填写的志愿进行选择，如果老师已经收满或者其他老师没招满，就会进行分配。5）关于官网上的一些小细节：大家知道每年三小院可能都会有调剂名额（国科、钢协、AI院(这个刚开，所以考生质量不稳定)）之前有年钢协学院把两个一志愿考生刷掉，招收调剂的情况。所以在官网看到下面几个图形，突然感觉是不是暗示着什么：国科的复试方案国科这边虽然计科只有一人上线，复试比例是1：1，但是明确标注了不收调剂。到目前为止也确实没有出现刷一志愿的情况。钢协的复试方案AI院的复试方案钢协和AI院的复试比例为1:1的时候，写道“根据一志愿复试合格考生人数待定”，同时在调剂计划中也列出了此专业，并说明人数待定。所以加上之前钢协院刷一志愿的情况，猜测如果这个人表现不好，大概率是会被刷掉然后招收调剂生源的。2. 复试经验1）笔试549计算机基础综合二(包含操作系统、计算机体系结构、软件工程)
推荐书目：可以用自己再学校里学过的教材。因为我两门没学过，说一下我用的。
《计算机体系结构》尹朝庆(包括配套的一个习题解析)
《计算机操作系统》汤小丹+王道操作系统
《软件工程导论》张海藩(北科用这个)
其实我本身20年第一年网络复试没有考机试和笔试，恰好我当时也没怎么学，所以可以提供的经验不是特别多hhh。不过从21年题目来看，出题并不是很刁钻，还是把资料里内容复习好了，基本上问题不大。2）机试
资料里有提供 王道的机试指南，以及算法笔记(这个是结合PAT网站的题目一起刷，对PAT里的题目根据知识点进行了分类汇总，每一道也都有答案)还有一个Leecode刷题笔记(这个是结合Leecode网站刷代码用的)。
根据电子书上的总结搭配对应在线OJ，多加练习，熟能生巧。3） 面试(核心：老师会接着你的话说，要学着挖坑给老师跳)
北科的面试基本上可以分为三部分：英语面试、专业面试和综合素质面试。 英语面试：首先准备好一个英文自我介绍。需要精心准备一下，因为有可能老师会根据你说的自我介绍继续问。比如你说在校期间参加了什么什么比赛，老师可能就问你“Can you describe what you did in this project”。也有可能只是单纯的和你聊一下，比如“What is your best subject”，这时候你说一个，老师就会接你的话继续问：“What do you need to do to learn this course well”。也有可能是问一些计算机相关的问题：“What is your most interesting direction in computer science”，这时候你随便说一个，老师就会接着问你”Do you have any practice in this direction“专业面试：这个是因为20年我们没有笔试嘛，所以专业课考察放在面试里问了，21复试的时候有的组就没有问专业知识。不过相应的还是准备一下。很多情况下会以”你计算机基础科目中学的最好的是什么科目“开始，你只要说了，接下来的问题就是围绕这个科目的问题。而且是由浅入深，直到问到你不会。当时20年我们是从20个题目中随机选3个题目问。涉及到的科目有数据库、编译原理、操作系统。如果你回答不上来了，老师可能会引导你一下，比如当时我抽中一个编译原理的题目，但是我没有复习，老师问你学过编译原理吗，我说没有学过，老师就让我想一下在电脑上编写程序的时候，从编写程序到这个程序运行都会经历什么阶段，想引导一下我。综合面试：这个部分就不太涉及专业课的知识了，可能会关注你本科经历多一点。可以事先准备好一份简历，线下复试就发给老师一人一份，他们看着简历会从里面问你问题(所以可以在简历里写上你比较擅长的东西)。线上复试之前会让你上传相应资料，可以把简历上传一下，老师也会看到。我在简历上写了参加的比赛，老师会围绕这个比赛你做了什么事情，解决了什么问题来问一下还会根据你本科专业问一些相关的问题，因为我本科是物联网，老师会问一下物联网相关的技术概念，问我你觉得从物联网来到计算机科学有什么优势，或者是你能干什么。总结一下就是老师会根据你提供的信息来问你问题，因为老师面试并不是想让你尴尬，也想让你有话说，所以基本上都是根据你说了什么他就会问你什么，所以可以提前想好自己说话内容，防止自己给自己挖坑了。小tips：因为面试是由规定一个人的时长大概10-15min，如果你回答问题比较快，说的比较少，可能5Min就进行完了。但是老师需要凑够时长，就只能问你专业课知识了，所以尽量会说的多说一点，说慢一点，不然老师随口一个专业课知识你可能都不会。面试整个过程保持住一个比较自然的状态是很重要的，其实遇到不会的并不是一个大问题，最大的问题就是你面对一个不会的问题呆住了，不知道怎么处理，整个场面很尴尬，让老师不舒服，这个分数就会很低。面对不会的，可以沉思一小会，然后大大方方的说：”老师，这个问题我目前没有想到怎么来解答（可能是因为我没学过这个科目/因为我对这个科目的掌握程度不够）”，如果能联想到相关的方面，你可以说：”不过这个问题让我想到XXXX，我认为XXX“说一下你的见解。如果你什么也想不到，就说：”我之后会去看看相关知识点,.....“。面试其实不光看你一个知识储备，给人的印象也是很加分的，所以如果你知识储备不太够，就尽量表达和行为都得体：吐字要清晰，不要有很大的口音，老师会听不清楚。 表情要自然，不要太过于紧张，就当做是和家里长辈聊天一样。 说话要有礼貌，一进去要说老师好，结束了要说老师辛苦了，如果老师引导你回答这个问题，记得谢谢老师。3. 关于联系导师1）联系导师的时间：初试结束：可以但没必要。初试成绩出了：有实力的大佬可以，有可能就和导师定了，普通人可以但没必要，老师会说欢迎报考。复试成绩出了：普通人可以行动了。虽然网上说越早越好，但是以我亲身经历来看，因为我比较普通，从初试结束就联系导师，很多不理你，有些会回复欢迎报考，不会和你深入交流。只有确认你被录取了，这时候找老师才会有老师愿意看一下你的情况。而我一个朋友本科的时候一作发了一篇SCI二区，初试结束联系老师，老师就加她微信仔细聊了。所以如果你没有收到回复也不用着急，只要录取了总会有老师hhh。2）发邮件需要的小技巧题目一定要突出，老师邮箱会收到大量的邮件，最好题目就突出你的目的，比如：[考研] 姓名+分数排名+本科院校+联系方式 内容一定要简洁突出，老师一般都比较忙，如果你写一大堆，没有突出重点可能不是很好看。建议：分条描述你想要展示的东西，不重要的就几个字带过，重要的多写一下。简历用图片的形式附在正文最后，你的相关文件可以作为附件加进去，但是老师不会为你而下载附件，最后把简历插在正文最后，老师扫一眼内容的时候正好可以看到你的简历。下面是一篇对于导师的认知经验帖子4.匠心考研复试549资料（欢迎来某宝加购~）九、调剂专栏我其实是二战生，一站北邮复试被刷所以经历过调剂。在这里分享一些基本的内容：1. 调剂出身很重要北京压分岂不是对调剂不利？（不会，更看本科学校）北科有校内调剂吗，计通不进复试可以调剂去其他三院吗？（如果本科是211及以上可以通过研招网进行调剂）多少分可以调剂北科？（分数不太重要，比较看本科学校）
因为每个学校自命题考题不一样，每个地区的得分情况也不一样，所以一般不会看分数筛选调剂生源。所以北京地区的压分对调剂的影响也比较小。 调剂最重要的还是本科出身，计算机考研饱和度已经很高了，不缺本科是985 211的高分学子。（我本身也是双非，以下并不是歧视双非，就是把我见过的情况说一下）。在我研究生生活中，我听过很多次，老师们一致认为985 211的学生会比双非学生好，所以调剂生源能招收到985 211的学生，老师肯定会优先选择的。计算机报考人数这么多，所以双非想要调剂好学校是难上加难。一般来说愿意接收你调剂请求的院校层次是≤你本科层次的。比如我调剂那年，因为我是一个双非一本，同意让我去调剂复试的是天津的一个双非二本，和北京的一个双非一本。北科是没有校内调剂的，是面向全国考生招收调剂生源的，没有校内调剂这个优惠政策。2. 调剂院校层次不高就要关注位置如果你真的不想二战，准备走调剂了，如1所说很难找到比你本科层次更好的学校。这个时候可以多关注一下地区。比如我调剂那年，一个天津二本和北京一本，或者再来个山东一本的话，那我肯定选择北京一本。计算机专业在北上广深的资源很多，留在这些地方可以多去实习、磨炼技术，毕业后也可以凭借自己的实力和经验去大厂面试。3. 调剂全过程①、调剂信息搜集（下一节我会单独说一下怎么搜集信息）②、锁定合适的院校，填写预调剂系统有很多院校的官网会设置一个预调剂系统，需要填写详细的个人履历和资料证明，主要目的是在研招网调剂开启之前筛选优秀人才，提前发offer，等研招网调剂系统开放，对这些人的申请会直接通过。填写完预调剂系统，如果院校觉得你合适，会通过你预留联系方式给你发复试通知，这个阶段都是在研招网调剂之前开始的。如果没有收到复试通知也不用着急，后面还可以通过研招网再次申请看看。③、找心仪的导师广发邮件询问这里要做好广撒网的准备，很多时候邮件都是有去无回，不用着急，尽力做就可以了，抓住一切机会。④ 、填报研招网调剂系统研招网的调剂系统有一个“调剂意向采集系统”和“调剂系统”，一般是在3月中下旬开始开放调剂意向采集系统调剂意向采集系统：可以填写10个调剂意向，在过两天开放的调剂系统中支持一键导入调剂系统调剂系统填写志愿真正调剂系统中只有三个志愿，填写好志愿后需要等待院校审核，这里有一个小tips:一般只填两个志愿，空一个位置！！因为每个志愿都会有一个锁定时间，比如A志愿如果院校不拒绝你，你只能在48小时候才可以填写新的志愿。对于调剂人来说，时间就是名额！但有很多学校查看了你的志愿就晾着你了，并不释放这个志愿的位置，如果你填满了三个，最后三个学校都占着茅坑不拉屎，你就无法选择其他学校了，所以先写两个，空一个位置以备不时之需。收到院校的复试通知之后，剩下的就是普普通通的复试流程啦，查看这个院校的复试内容准备一下，通过以后研招网会有待录取通知。希望每一个调剂人都能遇到双向奔赴的学校呀！4.调剂信息搜集单独说一下如何主动出击，掌握更加全面的调剂动态呢？第一点是留意研招网的调剂信息第二点是主动搜索和预测院校的调剂情况众所周知研招网有调剂专栏，如下图，不定时更新院校的调剂信息：其实在研招网的其他模块也会夹杂一些调剂信息，所以细心一点多留意一下哦，比如下图的模块。除了被动的接收研招网信息推送以外，我们也可以主动查询和预测院校的调剂情况，下图是研招网里的院校库，里面有全国的高校。Step 1: 如果你有心仪的城市，可以拿到这个城市里所有的学校：（去掉最好的学校，因为进不去；去掉最差的学校：因为不愿将就；剩下的学校就都是你的目标）Step 2： 遍历每一个学校，去研招网查看他们的通知，你需要关注的是：今年的招生目录今年的报考人数（观察有无报满？）上年的招生目录（和今年对比观察有无新增专业？）上年的调剂情况（观察这个院校之前有无调剂？调剂信息上年是何时公布的？调剂处的联系方式？）然后把每个学校的情况整理汇总出来，就可以预测每个学校有没有可能收调剂？大概什么时候出通知？是否有新增专业？等等，利用信息差去争取名额。一些小tips:因为北科是自命题，每个学校的初试专业课也不同，所以调剂时只要是相关专业的，都去试试！除非他明确限制了你的初试专业课必须是什么408。因为每个学校复试考察的并不相同，所以复试线边缘的考生不知道继续准备北科复试呢，还是应该准备调剂院校的复试。其实一开始你并不知道你会去哪个调剂院校参加复试，所以我的建议是先准备通用内容，比如先准备机试和面试（计算机基础学科知识，比如408），等后面确定参加哪里复试的时候再临阵磨枪看看笔试内容。

递推求解我们来看一个知名的数列一斐波那契数列。 这个数列是这样定义的，它的第一个数是1，第二个数也是1，其后的每一个数都是前两个数的和，即这样一个数列: 1、1、2、3、5、8、…这样，只要我们确定了这个数列的前两个数，那么后面的每一个数都能经过一次次的累加得到。即，当我们知道这个数列的开头几个数字，并确定它的递推规则，只需通过重复的递推就能得到这个数列的每一个数。利用递推解决问题，我们就要模仿求斐波那契数列的过程。首先，确定几个规模较小的问题答案。然后考虑如何由这几个规模较小的答案推得后面的答案。一旦有了递推规则和数列初始的几个值，计算机程序就能帮助我们求解数列后面的所有数字，我们的问题也得到了解决。Problem 1这个问题就是一个典型的递推问题。若我们把N分别等于1、2、3…的答案依次排列为一个数列，我们即需求这个数列每一个数的值。我们定义f[n]为数列中第n个数，同时F[n]为台阶总数为n时的上台阶方式总数。首先，当数据规模较小时我们可以直接得到答案，如F[1]=1, F[2]=2。其次，我们必须确定数列间的递推关系。当n大于2时，我们考虑每种上台阶方式的最后一步，由于只有两种行走的方法，因此它只可能是从n-1阶经过一步走到n阶，或者从n-2阶经过二步走到n阶。我们分别考虑这两种走法，即我们将此时所有的上楼梯方式按照最后一步走法的不同分成两类，分别确定这两类的上楼梯方式数目。经n-1阶到达n阶，因为其最后一步是确定的,所以上楼梯方式数量与原问题中到达n-1阶的方式数量相同，同为F[n-1]；同理，经n-2阶到达n阶,其上楼梯方式数量与原问题中到达n-2阶的方式数量相同，同为F[n- 2]。这样，我们就确定了达到n阶楼梯总的上楼方式个数为F[n- 1]和F[n-2]的和， 即F[n]=F[n- 1]+F[n-2]。这就是这个数列的递推关系。由初始值F[1]=1, F[2]=2，我们就能推得所有F[m]的值。#include <stdio.h>
long long F[91]; //F数组保存数列的每一个值，由于数值过大，我们需要使用long long类型
int main() {
F[1]=1;
F[2]=2; //数列初始值
for (int i=3;i<=90;i++)
F[i]=F[i-1]+F[i-2]; //递推求得数列的每一个数字
int n;
while (scanf("%d",&n) !=EOF) {
printf("%lld\n",F[n]);
}
return 0;
}
Problem 2同样的，在该例中我们也容易得到规模较小时的错装方式数量。如n为1时，数量为0; n为2时数量为1。我们按照n的取值顺序将所有的错装方式数量排列为一个数列，同样用F[n]表示数列里第n个数的取值，F[n]同时代表n个信封的错装方式总数，我们确定该数列的递推关系。当n大于3时，我们考虑n封信全部装错的情况。将信封按顺序由1到n编号。在任意一种错装方案中，假设n号信封里装的是k号信封的信，而n号信封里的信则装在m号信封里。我们按照k和m的等值与否将总的错装方式分为两类。若k不等于m,交换n号信封和m号信封的信后，n号信封里裝的恰好是对应的信，而m号信封中错装k号信封里的信，即除n号信封外其余n-1个信封全部错装，其错装方式等于F[n-1]，又由于m的n-1个可能取值，这类错装方式总数为(n-1) * F[n-1]。也可以理解为，在n-1个信封错装的F[n-1]种方式的基础上，将n号信封所装的信与n- 1个信封中任意一个信封(共有n-1中选择)所装的信做交换后，得到所有信封全部错装的方式数。另一种情况，若k等于m,交换n号信封和m号信封的信后，n号信封和m号信封里装的恰好是对应的信，这样除它们之外剩余的n-2个信封全部错装，其错装方式为F[n-2],又由于m的n-1个取值，这类错装方式总数为(n-1) * F[n-2]。也可以理解为，在n-2个信封全部错装的基础上，交换最后两个信封的信(n号信封和1到n-1号信封中任意一个，共有n-1种选择),使所有的信封全部错装的方式数。综上所述，F[n]=(n-1) * F[n- 1]+(n-1) * F[n-2]。这就是有名的错排公式。#include <stdio.h>
long long F[21]; //数值较大选用long long
int main() {
F[1]=0;
F[2]=1; //初始值
for(int i=3;i<=20;i++)
F[i]=(i-1)*F[i-1]+ (i-1)*F[i-2]; //递推求得数列每-一个数字
int n;
while (scanf("%d", &n)!=EOF) {
printf("%lld\n",F[n]);
}
return 0;
}
递推求解问题，根据输入的顺序，其答案往往排列成一个数列。为了求得数列中的每一个数字，我们首先得到输入规模较小时的答案，即数列开头的几个数字。分析问题，将每一个问题都分割成规模较小的几个问题，分割过程中要做到不遗漏不重复，并确定它们的关系从而得到递推关系式，利用它求出每一个输入所对应的答案。最长递增子序列(LIS)最长递增子序列是动态规划中最经典的问题之一，总结一下，求最长递增子序列的递推公式为:有序列{a1,a2…an}，我们求其最长递增子序列长度。按照递推求解的思想，我们用F向代表若递增子序列以a结束时它的最长长度。当i较小，我们容易直接得出其值，如F[1]= 1。那么，如何由已经求得的F[i]值推得后面的值呢?假设，F[1]到F[x-1]的值都已经确定，注意到，以ax结尾的递增子序列，除了长度为1的情况，其它情况中, ax都是紧跟在一个由ai(i<x)组成递增子序列之后。要求以a结尾的最长递增子序列长度，我们依次比较ax与其之前所有的ai(i <x)，若ai小于ax，则说明ax可以跟在以ai结尾的递增子序列之后，形成一个新的递增子序列。又因为以a结尾的递增子序列最长长度已经求得,那么在这种情况下，由以ai结尾的最长递增子序列再加上ax得到的新的序列，其长度也可以确定,取所有这些长度的最大值，我们即能得到F[x]的值。特殊的，当没有ai(i <x)小于ax,，那么以ax结尾的递增子序列最长长度为1。即F[x]=max{1, F[i]+1
ai< ax&&i<x};由题意不难看出，要求最多能够拦截多少枚导弹，即在按照袭击顺序排列的导弹高度中求其最长不增子序列。所谓不增子序列，即子序列中排在前面的数字不比排在后面的数字小。求最长不增子序列的原理与求最长递增子序列的原理完全一致，只是递推关系相应的发生一些变化，递推关系如下:#include <stdio.h>
int max(int a,int b) {return a > b? a:b;} //取最大值函数
int list[26]; //按袭击事件顺序保存各导弹高度
int dp[26]; //dp[i]保存以第i个导弹结尾的最长不增子序列长度
int main(){
int n;
while(scanf("%d",&n) !=EOF) {
for(int i=1;i<=n;i++){
scanf("%d",&list[i]);
}
for (int i=1;i<=n;i++) { //按照袭击时间顺序确定每一个dp[i]
int tmax=1; //最大值的初始值为1,即以其结尾的最长不增子序列长度至少为1
for(int j=1;j<i;j++){//遍历其前所有导弹高度
if (list[j] >= list[i]) { //若j号导弹不比当前导弹低
tmax=max(tmax, dp[j] + 1); //将当前导弹排列在以j号导弹结尾的最长不增子序列之后，计算其长度dp[j]+1, 若大于当前最大值，则更新最大值
}
}
dp[i]=tmax; //将dp[i]保存为最大值
}
int ans=1;
for(int i=1;i<=n;i++){
ans=max(ans,dp[i]);
} //找到以每一个元素结尾的最长不增子序列中的最大值，该最大值即为答案
printf("%d\n",ans);
}
return 0;
}
其时间复杂度为O (n*n)，空间复杂度为O (n)。由上例的分析过程可知，最长递增子序列问题的求解思想，不仅可以用来解决单纯的最长递增子序列问题，也可以经过类比来求解其它大小关系确定的子序列最长长度。最长公共子序列(LCS)有两个字符串S1和S2，求一个最长公共子串，即求字符串S3，它同时为S1和S2的子串，且要求它的长度最长，并确定这个长度。这个问题被我们称为最长公共子序列问题。与求最长递增子序列一样，我们首先将原问题分割成一些子问题，我们用dp[i][j]表示S1中前i个字符与S2中前j个字符分别组成的两个前缀字符串的最长公共子串长度。显然的，当i、j较小时我们可以直接得出答案，如dp[0][i]必等于0。那么，假设我们已经求得dp[i][j] (0<=i<x,0<=j<y)的所有值，考虑如何由这些值继而推得dp[x][y]，求得S1前x个字符组成的前缀子串和S2前y个字符组成的前缀子串的最长公共子序列长度。若S1[x]==S2[y]，即S1中的第x个字符和S2中的第y个字符相同，同时由于他们都是各自前缀子串的最后一个字符，那么必存在一个最长公共子串以S1[x]或S2[y]结尾，其它部分等价于S1中前x-1个字符和S2中前y-1个字符的最长公共子串。所以这个子串的长度比dp[x-1][y-1]又增加1，即dp[x][y] =dp[x-1][y-1]+1。相反的，若S1[x]!= S2[y]，此时其最长公共子串长度为S1中前x-1个字符和S2中前y个字符的最长公共子串长度与S1中前x个字符和S2中前y-1个字符的最长公共子串长度的较大者，即在两种情况下得到的最长公共子串都不会因为其中一个字符串又增加了一个字符长度发生改变。综上所述，dp[x][y]=max {dp[x-1][y]，dp[x][y-1]}。最长公共子序列问题的递推条件：假设有两个字符串S1和S2,其中S1长度为n，S2长度为m，用dp[i][j]表示S1前i个字符组成的前缀子串与S2前j个字符组成的前缀子串的最长公共子串长度，那么：由这样的递推公式和显而易见的初始值，我们即能依次求得各dp[i][j]的值，最终dp[n][m]中保存的值即为两个原始字符串的最长公共子序列长度。#include <stdio.h>
#include <string.h>
int dp[101][101];
int max(int a,int b) {return a>b? a:b;} //取最大值函数
int main(){
char S1[101],S2[101];
while(scanf("%s%s",S1,S2)!=EOF) {
int L1=strlen(S1);
int L2=strlen(S2); //依次求得两个字符串的长度
for(int i=0;i<=L1;i++) dp[i][0]=0;
for(int j=0;j<=L2;j++) dp[0][j]=0; //初始值
for(int i=1;i<=L1;i++){
for (int j=1;j<=L2;j++) { //二重循环依次求得每个dp[i][j]值
if(S1[i-1]!=S2[j-1])
//因为字符串数组下标从0开始，所以第i个字符位置为S1[i-1],若当前两个字符不相等
dp[i][j]=max(dp[i][j-1],dp[i-1][j]); //dp[i][j]为dp[i][j-1]和dp[i-1][j]中较大的一个
else dp[i][j]=dp[i-1][j-1]+1; //若它们相等，则dp[i][j]比dp[i-1][j-1]再加一
}
}
printf("%d\n",dp[L1][L2]);
}
return 0;
}
其时空复杂度都是O(L1 * L2)，其中L1和L2分别为两个字符串的长度。状态与状态转移方程回顾两种经典问题的算法模式，我们都先定义了一个数字量，如最长递增子序列中用dp[i][j]表示以序列中第i个数字结尾的最长递增子序列长度和最长公共子序列中用dp[i][j]表示的两个字符串中前i、j个字符的最长公共子序列，我们就是通过对这两个数字量的不断求解最终得到答案的。这个数字量就被我们称为状态。状态是描述问题当前状况的一个数字量。首先，它是数字的，是可以被抽象出来保存在内存中的。其次，它可以完全的表示一个状态的特征，而不需要其他任何的辅助信息。最后，也是状态最重要的特点，状态间的转移完全依赖于各个状态本身，如最长递增子序列中，dp[x]的值由dp[i] (i<x)的值确定。若我们在分析动态规划问题的时候能够找到这样一个符合以上所有条件的状态，那么多半这个问题是可以被正确解出的。这就是为什么人们常说，做DP题的关键，就是寻找一个好的状态。动态规划问题分析举例Problem 1在选定的最优方案中，每对物品都是重量相邻的一对物品。在得出这个结论后，我们设计描述该问题的状态。首先将所有物品按照重量递增排序，并由1到n编号。设dp[i][j]为在前j件物品中选择i对物品时最小的疲劳度，那么根据物品j和物品j-1是否被配对选择，该状态有两个来源：若物品j和物品j-1未被配对，则物品j一定没被选择，所以dp[i][j]等价于dp[i][j-1]；若物品j和物品j-1配对，则dp[i][j]为dp[i-1][j-2]再加上这两件物品配对后产生的疲劳度，即前j-2件物品配成的i-1对再加上最后两件配成的一对物品，共得到i对物品。初始时，dp[0]为 0，即不选择任何一对物品时，疲劳度为0。综上所述，其状态转移方程为(设经过排序后第i件物品重量为list[i])：#include <stdio.h>
#include <algorithm>
using namespace std;
#define INF 0x7ffffff //预定义最大的int取值为无穷
int list[2001]; //保存每个物品重量
int dp[1001][2001]; //保存每个状态
int main(){
int n,k;
while (scanf("%d%d",&n, &k) != EOF) {
for(int i=1;i<=n;i++){
scanf("%d", &list[i]);
}
sort(list+1,list+1+n); //使所有物品按照重量递增排序
for(int i=1;i<=n;i++) //初始值
dp[0][i]=0;
for(int i=1;i<=k;i++){//递推求得每个状态
for(int j=2*i;j<=n;j++){
if(j>2*i)
/*若j>2*i则表明，最后两个物品可以不配对，即前j-1件物品足够
配成i对，dp[i][j]可以由dp[i][j-1]转移而来，其值先被设置为dp[i][j-1]*/
dp[i][j]=dp[i][j-1];
else
dp[i][j]=INF;
/*若j==2*i,说明最后两件物品必须配对，否则前j件物品配不
成对，所以其状态不能由dp[i][j-1]转移而来，dp[i][j]先设置为正无穷*/
if (dp[i][j] > dp[i-1][j-2] + (list[j]-list[j-1])*(list[j]-list[j-1]))
/*若dp[i][j]从dp[i-1][j-2]转移而来时，其值优于之前确定的
正无穷或者由dp[i][j-1]转移而来的值时，更新该状态*/
dp[i][j]=dp[i-1][j-2]+(list[j]-list[j-1])*(list[j]-list[j-1]); //更新
}
}
printf("%d\n", dp[k][n]);
}
return 0;
}
Problem 2本题大意:有一堆柑橘，重量为0到2000,总重量不大于2000。要求我们从中取出两堆放在扁担的两头且两头的重量相等，问符合条件的每堆重量最大为多少。没有符合条件的分堆方式则输出-1。首先，我们只考虑柑橘重量为非0的情况。因为本题要求解的是重量相等的两堆柑橘中每堆的最大重量,并且在堆放过程中，由于新的柑橘被加到第一堆或者第二堆，两堆之间的重量差会动态发生改变，所以我们设状态dp[i][j]表示前i个柑橘被选择后(每个柑橘可能放到第一堆或者第二堆)后，第一堆比第二堆重j时(当j为负时表示第二堆比第一堆重)，两堆的最大总重量和。初始时，dp[0][0]为 0,即不往两堆中加任何柑橘时，两堆最大总重量为0；dp[0][j] (j不等于0)为负无穷，即其它状态都不存在。根据每一个新加入的柑橘被加入到第一堆或者第二堆或者不加到任何堆，设当前加入柑橘重量为list[i]， 这将造成第一堆与第二堆的重量差增大list[i]或减小list[i]或者不变，我们在它们之中取最大值，其状态转移为：当根据该状态转移方程求出所有的状态后，状态dp[n][0]/2即是所求。我们再来考虑柑橘重量包含0的情况，当在不考虑柑橘重量为0，推得dp[n][0]为正数时，柑橘重量为0的柑橘将不对答案造成任何影响，固在这种情况时可直接排除重量为0的柑橘。当在不考虑柑橘重量为0，推得dp[n][0]为0时，即不存在任何非0的组合使两堆重量相等。此时，若存在重量为0的柑橘，则可组成两堆重量为0的柑橘(至少有一个柑橘重量为0)，它们重量相等；否则，将不存在任何分堆方式，输出-1。#include <stdio.h>
#define OFFSET 2000
/*因为柑橘重量差存在负数的情况，即第一堆比第二堆轻，所以在计算重量差对应的数
组下标时加上该偏移值，使每个重量差对应合法的数组下标*/
int dp[101][4001]; //保存状态
int list[101]; //保存柑橘数量
#define INF 0x7ffffff //无穷
int main(){
int T;
int cas=0; //处理的Case数，以便输出
scanf("%d",&T); //输入要处理的数据组数
while (T--!=0) { //T次循环
int n;
scanf("%d",&n);
bool HaveZero =false; //统计是否存在重量为0的柑橘
int cnt=0;//t数器，记录共有多少个重量非零的柑橘
for (int i=1;i<=n;i++) { //输入n个柑橘重量
scanf("%d",&list[++cnt]);
if(list[cnt]==0) { //若当前输入柑橘重量为
cnt --; //去除这个柑橘
HaveZero=true; //并记录存在重量为0的柑橘
}
}
n=cnt;
for (int i=-2000;i <= 2000;i++) {
dp[0][i+OFFSET]=-INF;
} //初始化，所有dp[0][i]为负无穷。注意要对重量差加上OFFSET后读取或调用
dp[0][0+OFFSET]=0; //dp[0][0]为0
for(int i=1;i<=n;i++){//遍历每个柑橘
for (int j=-2000;j<=2000;j ++) {//遍历每种可能的重量差
int tmp1=-INF, tmp2=-INF; //分别记录当前柑橘放在第一堆或第二堆时转移得来的新值若无法转移则为-INF
if (j + list[i] <= 2000 && dp[i-1][j + list[i] + OFFSET] !=-INF) { //当状态可以由放在第一堆转移而来时
tmp1=dp[i-1][j+list[i]+OFFSET]+list[i]; //记录转移值
}
if (j - list[i] >=-2000 &&dp[i-1][j-list[i]+OFFSET]!=-INF) { //当状态可以由放在第二堆转移而来时
tmp2=dp[i-1][j-list[i]+OFFSET]+list[i]; //记录该转移值
}
if (tmp1 < tmp2) {
tmp1=tmp2;
} //取两者中较大的那个，保存至tmp1
if (tmp1 < dp[i-1][j+OFFSET]) { //将tmp1与当前柑橘不放入任何堆即状态差不发生改变的原状态值比较，取较大的值保存至tmp1
tmp1=dp[i-1][j+OFFSET];
}
dp[i][j+OFFSET]=tmp1; //当前值状态保存为三个转移来源转移得到的新值中最大的那个
}
}
printf("Case %d: ",++cas);//按题目输出要求输出
if (dp[n][0+OFFSET]==0) { //dp[n][0]为0
puts( HaveZero==true ? "0" : "-1");//根据是否存在重量为0的柑橘输出0或-1
}
else printf(" %d\n", dp[n][0+OFFSET]/2); //否则输出dp[n][0]/2
}
return 0;
}
背包问题Problem 1首先我们将这个问题抽象:有一个容量为V的背包，和一些物品。这些物品分别有两个属性，体积w和价值v,每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。因为最优解中，每个物品都有两种可能的情况，即在背包中或者不存在(背包中有0个该物品或者1个)，所以我们把这个问题称为0-1背包问题。在该例中，背包的容积和物品的体积等效为总共可用的时间和采摘每个草药所需的时间。在众多方案中求解最优解，是典型的动态规划问题。为了用动态规划来解决该问题，我们用dp[i][j]表示在总体积不超过j的情况下，前i个物品所能达到的最大价值。初始时，dp[0][j] (0<=j<=V)为 0。依据每种物品是否被放入背包，每个状态有两个状态转移的来源。若物品i被放入背包，设其体积为w，价值为v，则dp[i][j] =dp[i- 1][j-w]+v。即在总体积不超过j-w时前i-1件物品可组成的最大价值的基础上再加上i物品的价值v；若物品不加入背包,则dp[i][j] = dp[i-1][j]，即此时与总体积不超过j的前i-1件物品组成的价值最大值等价。选择它们之中较大的值成为状态dp[i][j]的值。综上所述，0-1 背包的状态转移方程为：转移时要注意，j-w的值是否为非负值，若为负则该转移来源不能被转移。#include <stdio.h>
#define INF 0x7fffffff
int max(int a,int b) {return a > b ? a: b;} //取最大值函数
struct E{ //保存物品信息结构体
int w; //物品的体积
int v; //物 品的价值
}list[101];
int dp[101][1001]; //记录状态数组，dp[i][j]表示前i个物品组成的总体积不大于的最大价值和
int main(){
int s,n;
while(scanf("%d%d",&s,&n) !=EOF) {
for(int i=1;i<=n;i++){
scanf("%d%d",&list[i].w,&list[i].v);
}
for(int i=0;i<=s;i++){
dp[0][i]=0;
} //初始化状态
for (int i=1;i<=n;i++) { //循环每一个物品
for (int j=s;j>=list[i].w;j--) {
//对s到list[i].w的每个j，状态转移来源为dp[i-1][j]或dp[i-1][j-list[i].w]+list[i].v, 选择其中较大的值
dp[i][j]=max(dp[i-1][j],dp[i-1][j-list[i].w]+list[i].v);
for (int j=list[i].w-1;j>=0;j--)
//对list[i].w-1到0的每个j，状态仅能来源于dp[i-1][j], 固直接赋值
dp[i][j]=dp[i-1][j];
}
}
printf("%d\n",dp[n][s]);
}
return 0;
}
观察状态转移的特点，我们发现dp[i][j]的转移仅与dp[i-1][j-list[i].w]和dp[i-1][j]有关， 即仅与二维数组中本行的上一行有关。根据这个特点，我们可以将原本的二维数组优化为一维，并用如下方式完成状态转移:为了保证状态正确的转移，我们必领保证在每次更新中确定状态dp[j]时，dp[j]和dp[i-1][j-list[i].w]尚未被本次更新修改。考虑到j-list[i].w<j, 那么在每次更新中倒序遍历所有j的值，就能保证在确定dp[j]的值时，dp[j- list[i].w]的值尚未被修改，从而完成正确的状态转移。#include <stdio.h>
#define INF 0x7fffffff
int max(int a,int b){return a>b?a:b;}//取最大值函数
struct E { //表示物品结构体
int w;
int v;
}list[101];
int dp[1001];
int main(){
int s,n;
while (scanf("%d%d",&s,&n) !=EOF) {
for(int i=1;i<=n;i++){
scanf("%d%d",&list[i].w,&list[i].v);
}
for(int i=0;i<=s;i++){
dp[i]=0;
} //初始值
for(int i=1;i<=n;i++){
for (int j=s;j>=list[i].w;j--) { //必须倒序更新每个dp[j]的值，j小于list[i].w的各dp[j]不作更新，保持原值，即等价于dp[i][j],dp[i-1][j]
dp[j]=max(dp[j],dp[j-list[i].w]+list[i].v); //dp[j]在原值和dp[j-list[i].w]+list[i].v中选取较大的那个
}
}
printf("%d\n",dp[s]);
}
return 0;
}
分析求解0-1背包问题的算法复杂度。其状态数量为n * s，其中n为物品数量，s为背包的总容积，状态转移复杂度为O(1)，所以综合时间复杂度为O(n*s)。经优化过后的空间复杂度仅为O(s) (不包括保存物品信息所用的空间)。0-1背包问题是最基本的背包问题，其它各类背包问题都是在其基础上演变而来。牢记0-1背包的特点：每一件物品至多只能选择一件，即在背包中该物品数量只有0和1两种情况。接着，我们扩展0-1背包问题，使每种物品的数量无限增加，便得到完全背包问题：有一个容积为V的背包，同时有n个物品，每个物品均有各自的体积w和价值v,每个物品的数量均为无限个，求使用该背包最多能装的物品价值总和。我们先按照0-1背包的思路试着求解该问题。设当前物品的体积为w,价值为v,考虑到背包中最多存放V/w件该物品，我们可以将该物品拆成V/w件，即将当前可选数量为无限的物品等价为V/w件体积为w、价值为v的不同物品。对所有的物品均做此拆分，最后对拆分后的所有物品做0-1背包即可得到答案。但是，这样的拆分将使物品数量大大增加，其时间复杂度为:可见，当S较大同时每个物品的体积较小时其复杂度会显著增大，固将该问题转化为0-1背包的做法较不可靠。但是由该解法可窥见0-1背包的重要性，很多背包问题均可以推到0-1背包上来。Problem 2题目大意:有一个储蓄罐，告知其空时的重量和当前重量，并给定一些钱币的价值和相应的重量，求储蓄罐中最少有多少现金。由于每个钱币的数量都可以有任意多，所以该问题为完全背包问题。但是在该例中，完全背包有两处变化，首先，要求的不再是最大值，而变为了最小值，这就要求我们在状态转移时，在dp[j]和dp[j-list[i].w]+list[i].v 中选择较小的转移值；其次，该问题要求钱币和空储蓄罐的重量恰好达到总重量，即在背包问题中表现为背包恰好装满，在前文中我们已经讨论了0-1背包的此类变化，我们只需变化dp[i]的初始值即可。#include <stdio.h>
#define INF 0x7fffffff
int min(int a,int b){return a<b?a:b;}//取最小值函数
struct E { //代表钱币结构体
int w; //重量
int v; //价值
}list[501];
int dp[10001]; //状态
int main() {
int T;
scanf("%d",&T); //输入测试数据组数
while (T--) { //T次循环，处理T组数据
int s,tmp;
scanf("%d%d",&tmp,&s); //输入空储蓄罐数量，和装满钱币的储蓄罐重量
s-=tmp; //计算钱币所占重量
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&list[i].v,&list[i].w);
}
for(int i=0;i<=s;i++){
dp[i]=INF;
}
dp[0]=0; //因为要求所有物品恰好装满，所以初始时，除dp[0]外，其余dp[j]均为无穷(或者不存在)
for(int i=1;i<=n;i++){//遍历所有物品
for (int j=list[i].w;j<=s;j++) { //完全背包，顺序遍历所有可能转移的状态
if (dp[j-list[i].w]!=INF) //若dp[j-list[i].w]不为无穷，就可以由此状态转移而来
dp[j]=min(dp[j],dp[j-list[i].w]+list[i].v); //取 转移值和原值的较小值
}
}
if (dp[s] != INF) //若存在一种方案使背包恰好装满，输出其最小值
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[s]);
else //若不存在方案
puts("This is impossible.");
}
return 0;
}
总结一下完全背包问题,其特点为每个物品可选的数量为无穷,其解法与0-1背包整体保持一致，与其不同的仅为状态更新时的遍历顺序。时间复杂度和空间复杂度均和0-1背包保持一致。最后，我们介绍多重背包问题，其介于0-1背包和完全背包之间:有容积为v的背包，给定一些物品，每种物品包含体积w、价值v、和数量k,求用该背包能装下的最大价值总量。与之前的背包问题都不同，每种物品可选的数量不再为无穷或者1,而是介于其中的一个确定的数k。与之前讨论的问题一样，我们可以将多重背包问题直接转化到0-1背包上去，即每种物品均被视为k种不同物品,对所有的物品求0-1背包，其时间复杂度为:由此可见，降低每种物品的数量ki 将会大大的降低其复杂度，于是我们采用一种更为有技巧性的拆分。将原数量为k的物品拆分为若干组，每组物品看成一件物品，其价值和重量为该组中所有物品的价值重量总和，每组物品包含的原物品个数分别为:为: 1、 2、4…k-2c+1, 其中c为使k-2c+1大于0的最大整数。这种类似于二进制的拆分,不仅将物品数量大大降低，同时通过对这些若干个原物品组合得到新物品的不同组合,可以得到0到k之间的任意件物品的价值重量和，所以对所有这些新物品做0-1背包，即可得到多重背包的解。由于转化后的0-1背包物品数量大大降低，其时间复杂度也得到较大优化，为：Problem 3在该例中，对每个物品的总数量进行了限制，即多重背包问题。我们对每种物品进行拆分，使物品数量大大减少，同时通过拆分后的物品间的组合又可以组合出所有物品数量的情况。#include <stdio.h>
struct E{ //大米
int w; //价格
int v; //重量
}list[2001];
int dp[101];
int max(int a,int b){return a>b?a:b;}//取最大值函数
int main(){
int T;
scanf("%d",&T);
while (T --) {
int s,n;
scanf("%d%d",&s,&n);
int cnt=0; //拆分后物品总数
for(int i=1;i<=n;i++){
int v,w, k;
scanf("%d%d%d",&w,&v,&k);
int c=1;
while (k-c>0) { //对输入的数字k,拆分成1,2, 4...k-2^c + 1,其中c为使最后一项大于0的最大整数
k-=c;
list[++cnt].w=c*w;
list[cnt].v=c*v; //拆分后的大米重量和价格均为组成该物品的大米的重量价格和
c*=2;
}
list[++cnt].w=w*k;
list[cnt].v=v*k;
}
for (int i=1;i <=s;i++) dp[i]=0; //初始值
for (int i=1;i <= cnt;i++) { //对拆分后的所有物品进行0-1背包
for (int j=s;j >= list[i].w;j--) {
dp[j]=max(dp[j],dp[j -list[i].w] + list[i].v);
}
}
printf("%d\n",dp[s]);
}
return 0;
}
总结多重背包问题:多重背包的特征是每个物品可取的数量为一个确定的整数，我们通过对这个整数进行拆分，使若干个物品组合成一个价值和体积均为这几个物品的和的大物品，同时通过这些大物品的间的组合又可以组合出选择任意件物品所包含的体积和重量情况，通过这种拆分使最后进行0-1背包的物品数量大大减少，从而降低复杂度，其时间复杂的为:空间复杂度与0-1背包保持一致。