理论说明 本节将要讨论动态规划问题中又一个十分常见，同时在机试中又是终点被考察的问题--背包问题。背包问题的变化之多让我们不容易一下子完全掌握它，根据考研机试的实际需要，我们在本节中主要讨论0-1背包、完全背包和多重背包这三类背包问题。 题目来源 2008年北京大学图形学实验室计算机研究生机试真题 题目描述 辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。 为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。 医师把他带到个到处都是草药的山洞里对他说： “孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。 我会给你一段...

理论说明 在之前的LCS、递推等中，我们已经梳理了一些较为经典的动态规划问题的解法，本节将对这两种算法进行总结，并探讨解动态规划问题的统一思路。 回顾两种典型问题的算法模式，我们都首先定义了一个数字量，如最长递增子序列中用dp[i]表示以序列中第i个数字结尾的最长递增子序列长度和最长公共子序列中用dp[i][j]表示的两个字符串中前i,j个字符的最长公共子序列，我们就是通过对这两个数字量的不断求解得到答案的。这个数字量被我们称为状态。状态是描述问题当前状态的一个数字量。首先，它是数字的，是可以被抽象出来保存在内存中的。其次，它可以完全的表示一个状态的特征，而不需要其他任何的辅助信息。最后，也是...

理论说明 有两个字符串S1和S2,求一个最长的公共子串，即求字符串S3,它同时为S1和S2的子串，且要求它的长度最长，并确定这个长度。这个问题被我们称为最长公共子序列问题。 与求最长递增子序列一样，我们首先将问题分割成一些子问题，我们用dp[i][j]表示S1中前i个字符与S2中前j个字符分别组成的两个前缀字符串的最长公共子串长度。显然的，当i、j较小时我们可以直接得到答案，如dp[0][j]必等于0.那么，假设我们已经求得dp[i][j]（0<=i<x，0<=j<y）的所有值，考虑如何由这些值继续推得dp[x][y],求得S1前x个字符组成的前缀子串和S2前y个字符组...

理论说明 最长递增子序列是动态规划中最经典的问题之一，我们讨论这个问题开始，循序渐进的了解动态规划的相关知识要点。 有序列{a1,a2,...,an}，我们求其最长递增子序列长度。按照递推求解的思想，我们用F[i]代表若递增序列以ai结尾时他的最长长度。当i比较小时，我们容易求解其值，如F[1]=1.那么，如何由已经求得的F[i]值推得后面的值呢？ 假设F[1]到F[x-1]的值都已经确定了，注意到，以ax结尾的递增子序列，除了长度1的情况，其他情况中，ax都紧跟在一个由ai(i<x)组成的递增子序列之后，要求以ax结尾的最长递增子序列的长度，我们依次比较ax与之前所有的ai（i<...

题目来源 2008年华中科技大学计算机保研机试真题 题目描述 N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归） 输入说明 输入包括一个整数N,(1<=N<90)。 输出说明 可能有多组测试数据，对于每组数据， 输出当楼梯阶数是N时的上楼方式个数。 样例展示 输入： 4 复制 输出： 5 问题分析 这个问题就是一个典型的递推问题。若我们把N分别等于1，2，3...的答案依次排列成一个数列，我们即需求这个数列每一个数的值。我们定义f[n]为数列中的第n个数字，同时F[n]为台阶总数为n时的上台阶方式总数。首先，我们必须确定数列之间的递推关系。当n大于2时...

题目描述 The doggie found a bone in an ancient maze, which fascinated him a lot.However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.The maze was a rectangle with sizes...

理论说明 本部分梳理递归，递归是一种非常常用的技巧，所谓递归即函数调用函数本身，调用的方式按照问题的不同人为定义，这种调用方式被称为递归调用。同时，为了不使这样的递归无限的发生下去，我们必须设定递归的出口，即当函数到达某种条件时停止递归。如求n阶层的递归程序如下： int f(int x) { if(x==0) return 1; else return x*F(x-1); } 其递归方式为，每次递归调用时函数的参数减1，每一个函数在等待递归函数返回时将其返回值与本函数的参数相乘后返回给上一层函数。为了防止这样的递归无限发生，我们设定了一个递归出口，即当参数变为0时停止递归，直接返回...

理论说明 题目来源和说明 九度OJ 题目描述 Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.魔王住在一个城堡里,城堡是一个ABC的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出...

理论说明 枚举是最简单也是最直白的搜索方式，它依次尝试搜索空间中所有的解，测试是否符合条件，若符合则输出答案，否则继续测试下一组解。 但是在使用枚举这种相对比较暴力的算法来解题时，我们对其时间复杂度要做特别的关注。枚举问题的时间复杂度往往需要与需要枚举的情况个数有关，因为我们必须不遗不漏的枚举每一种可能成为答案的情况。所以搜索空间越大，枚举的时间复杂度越高。所以，我们对某一问题进行枚举时，必须保证其时间复杂度在题目时限可以接收的范围内。 题目来源和说明 2009年哈尔滨工业大学计算机研究生机试真题 题目描述 用小于等于n元去买100只鸡，大鸡5元/只，小鸡3元/只，还有1/3元每只的一种小鸡，...

理论说明 本次我们主要苏里一下图论中的另一个经典问题--拓扑排序，并以该问题作为图论最后一个专题。 设有一个有向无环图DAG，对其进行拓扑排序即求其中结点的一个拓扑序列，对于所有的有向边（U,A），在该序列中结点U都排序在结点V之前。满足该要求的结点序列，我们称为满足拓扑次序的序列。求这个序列的过程，被称为拓扑排序。 基本算法： 将入度为0的结点放入队列 while(队列不空) { x=队列头 for(i in （与x相联的结点）) { 结点i的入度减少1 if(结点i的队列为0) 入队列 } } return 最后一个结...

理论说明 之前已经总结梳理完最小生成树之后，我们再来梳理一下图论中的另一个经典问题：最短路径问题。即寻找图中某两个特定结点之间的最短路径长度。所谓图上的路径，即从图中一个起始结点到一个终止结点途中经过的所有结点序列，路径的长度即所经过的边权和。 朴素Dijkstra算法 朴素 堆优化的Dijkstra算法 题目来源和说明 题目描述 输入说明 输出说明 样例展示 输入： 输出： C++代码 继续畅通工程 C++代码

英语太难啦，大致意思是这样的： 一个部落有n个村子，若干条道路，每个道路有它的花费，要修一条可以连接所有村子的路，保证花费最小，典型的最小生成树。 用例第一行是n个村子，之后的n-1行是道路信息 A 2 B 12 I 25 这代表有两条路通往村子A，AB之间的花费是12，AI之间的花费是25。这个理解了就好做多了 C++代码： #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=100; int T[N]; int find(i...

理论说明 本节我们了解图论中的一类经典问题---最小生成树。 在一个无向连通图中，如果存在一个连通子图包含原图中所有的结点和部分边，且这个子图中不存在回路，那么我们称这个子图为原图的一棵生成树。在带权图中，所有的生成树中边权的和最小的数（可能不唯一），被称为最小生成树。 最小生成树问题是图论的经典问题之一，它在实际生活中也有广泛的应用，如在通信基站之间修建通信光缆使所有的基站之间可以直接或者间接通信，最少需要多少长的光缆。要利用最小生成树来解决实际问题，我们必须先学会怎么求解连通图的最小生成树。 这里介绍Kruskal算法的基本步骤： 初始时所有结点属于孤立的结点 按照边权顺序遍历所有...

理论说明 并查集的作用： 判断两个元素是否再同一集合中 求集合中元素的数量等 这里用树结构来表示集合。 那么如何判断两个元素是否再同一集合中？ 我们可以利用一个数组，数组单元i保存结点i的父节点编号，若该结点已经是根结点，则其双亲结点信息保存为-1.有了这样的存储结构，我们就能通过不断地求双亲结点来找到该节点所在树的根节点，若两个元素所在的根节点相同，则判断他们在同一颗树上，它们同属于一个集合。 对于合并两个集合，我们该如何操作和？ 我们可以让费别代表两个集合的两颗树进行合并，合并的方法为其中一颗树变为另一颗树根节点的子树，如下图所示 题目来源和说明 2005年浙江大学计...