东南大学2015春算法试卷答案.pdf

1、求解下面的递归式，并针对每个递推式给出一个界限。 （1） 7/7T nT nn 解： 7/7T nT nn， 其中 7,7,abf nn。 因此， 1 loglog 1 ba nnnn， 由于 f nnn，应用主定理第二条定理有， log loglog ba T nnnnn。 （2） 3/2 8/6logT nT nnn 解 ： 3/2 8/6logT nT nnn， 其 中 3/2 8,6,logabf nnn。 因 此 ， 6 loglog 80.778 ba nnn，由于 6 log 83/2 logf nnnn ，其中0.8，应用主 定理情况 3，当n足够大时，对于8/64/3c ，有： 3/2 /8/6 log/64/3logaf n bf nnnncf n，条件成立。因此，应用情 况 3 有， 3/2 logT nnn。 （3） 1/3 21T nT n 解：做代换2mn ，只考虑 1/3 n为整数的情形。可以得到， /3 2221 mm TT， 将此式改写为： 2/31S mS m。 对此式应用主定理情况 1，可以得到 3 loglog 2 ba S mmm，所以： 3 3 log 2 log 2 2 2log m T nTS mmn 22 2/31 1 2 1 2/3.1 22.2/3 kk S mS mS mS m ， 当 /31 k m时， 有， 3 logkm， 所以 33 loglog1 1 2 .2121 mm S mS ， 因此， 3 33 log 2 loglog 2 2 22log mm T nTS mmn 2、给出一个求解背包问题的算法。并说明其正确性。 输入：给定n个物品，物品价值分别为 12 , n P PP物品重量分别 12 , n W WW，背 包容量为M。每种物品可部分装入到背包中。 输出： 12 ,01 ni X XXX，使得 1 ii i n PX 最大，并且满足 1 ii i n W XM 。 解：这个问题的特点是：每种物品只有一件，可以选择放或者不放。利用动态规 划思想 ，子问题为：假设( , )f i j表示剩余容量为j，剩余物品为,1,.,i in 时的最优解的值。DP 求解过程可以这样理解： 对于前件物品，背包剩余容量为时，所取得的最大价值只依赖于两个状态。 状态状态 1 1：只要不选第个物品,前1i件物品，背包剩余容量为j。在该状态下， 1f ij。 状态状态 2 2：选第个物品,前1i件物品，背包剩余容量为 jW i。在该状态下, 1f ij W iP i 因为，这里要求最大价值，所以只要从状态 1 和状态 2 中选择最大价值较大 的一个即可。 （1）采用二维数组 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include using namespace std; int main() static const int M = 10; / 定义空间最大值 static const int n = 5; / 物品个数 vector dp(n + 1, vector(M + 1, 0); vector W(n + 1), P(n + 1); for (int i = 1; i Wi Pi; / 输入物品i的体积和价值 for (int i = 1; i Wi Pi; / 输入物品i的体积和价值 for (int i = 1; i = Pi; -j) / 对每一个状态进行比较 / 按照状态转移方程进行比较 dpj = max(dpj, dpj - Wi + Pi); cout n k) vector a(n + 1); vector sum(n + 1, vector(n + 1, 0); vector dp(n + 1, vector(k + 1, 0); for (int i = 1; i ai; / 输入待求数组 for (int i = 1; i = n; i+) for (int j = i; j = n; j+) int s = 0; for (int k = i; k = j; k+) s += ak; / sumij初始化为待求数组i到j的和 sumij = s; for (int i = 1; i = n; i+) dpi0 = sum1i;/ dpi0为1到i中，乘号个数为0时，数组的最大结果 for (int j = 1; j = k; j+) / 不断的添加乘号，动态规划求最大值 for (int i = j + 1; i = n; i+) / 添加乘号时，起始计算位是j+1 dpij = -1; / 开始动态规划 for (int k = j; k i; k+) dpij = max(dpij, dpkj - 1 * sumk + 1i); / 自底向上根据状态转移方程求最大值 cout dpnk; return 0; 6、给定n个任务以及m个机器，每个任务所需的处理时间为 12 , n p pp。一个 任务可由任一台机器执行，但