计算机算法设计与分析期终考试复习题.docx

《计算机算法设计与分析期终考试复习题.docx》由会员分享，可在线阅读，更多相关《计算机算法设计与分析期终考试复习题.docx（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -运算机算法设计与分析复习题一、填空题1、一个算法复杂性的高低表达在运算机运行该算法所需的时间和储备器资源上， 因此算法的复杂性有时间复杂性和空间复杂性之分。 2、出自于“平稳子问题”的思想，通常分治法在分割原问题，形成如干子问题时，这些子问题的规模都大致相同。3、使用二分搜寻算法在n 个有序元素表中搜寻一个特定元素，在正确情形下，搜寻的时间复杂性为O（1），在最坏情形下， 搜寻的时间复杂性为O（logn）。4、已知一个分治算法耗费的运算时间Tn ，Tn 满意如下递归方程：可编辑资料 - - - 欢迎下载精

2、品名师归纳总结T n O 12T n / 2 n2O n n2可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结解得此递归方可得Tn= O （n logn）。可编辑资料 - - - 欢迎下载精品名师归纳总结5、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过 的子问题建立了备忘录以备需要时查看，同样也可防止相同子问题的重复求解。 6 递归的二分查找算法在divide 阶段所花的时间是O1，conquer 阶段所花的时间是Tn/2，算法的时间复杂度是O log n。7 Pr

3、im算 法 利 用 贪 心策 略 求 解最 小 生 成 树 问 题 ， 其 时 间 复 杂 度是On2 。8背包问题可用贪心法，回溯法等策略求解。9用动态规划算法运算矩阵连乘问题的最优值所花的时间是On3， 子问题空间大小是On2。10图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是mn，解空间树中每个内结点的孩子数是m。11单源最短路径问题可用贪心法、分支限界等策略求解。12、一个算法的优劣可以用（时间复杂度 ）与（ 空间复杂度 ）与来衡量。13、回溯法在问题的解空间中， 按（深度优先方式 ）从根结点动身搜寻解空间树。14、直接或间接的调用自身的算法称为（递归算法 ）。15、记号在算

4、法复杂性的表示法中表示（渐进确界或紧致界 ）。16、在分治法中， 使子问题规模大致相等的做法是出自一种（ 平稳banlancing子问题 ）的思想。17、动态规划算法适用于解（具有某种最优性质 ）问题。18、贪心算法做出的挑选只是（在某种意义上的局部 ）最优挑选。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -19、最优子结构性质的含义是（问题的最优解包

5、含其子问题的最优解）。20、回溯法按（ 深度优先 ）策略从根结点动身搜寻解空间树。21、拉斯维加斯算法找到的解肯定是（正确解 ）。22、依据符号 O 的定义 Of+Og 等于 Omaxfn,gn。23、二分搜寻技术是运用（分治）策略的典型例子。24、动态规划算法中，通常不同子问题的个数随问题规模呈（多项式 ）级增长。25、（ 最优子结构性质 ）和（ 子问题重叠性质 ）是采纳动态规划算法的两个基本要素。26、（ 最优子结构性质 ）和（ 贪心挑选性质 ）是贪心算法的基本要素。27、（ 挑选能产生最优解的贪心准就）是设计贪心算法的核心问题。28、分支限界法常以（ 广度优先 ） 或（ 以最小耗费 最大

6、效益 优先 ）的方式搜寻问题的解空间树。29、贪心挑选性质是指所求问题的整体最优解可以通过一系列（ 局部最优 ）的挑选，即贪心挑选达到。30、依据活结点表的组织方式的不同，分支限界法包括 （ 队列式FIFO 分支限界法）和（ 优先队列式分支限界法）两种形式。31、假如对于同一实例， 蒙特卡洛算法不会给出两个不同的正确解答，就称该蒙特卡洛算法是（ 一样的）。32、哈夫曼编码可利用（ 贪心法 ）算法实现。33 概率算法有 数值概率算法，蒙特卡罗（ Monte Carlo ）算法，拉斯维加斯（ Las Vegas）算法和舍伍德（ Sherwood）算法34 以自顶向下的方式求解最优解的有（贪心算法

7、）35、以下算法中通常以自顶向下的方式求解最优解的是（贪心法 ）。36、在对问题的解空间树进行搜寻的方法中, 一个活结点有多次机会成为活结点的是（ 回溯法 ）37、旅行售货员问题不能用（）解决可以用回溯法解决，分支限界法，NP 完全性理论与近似算法38、贪心算法不能解决（ 0-1 背包问题N皇后问题 ）。可以解决背包问题39、投点法是（ 概率算法 ）的一种。40、如线性规划问题存在最优解，它肯定不在（可行域内部 ）二、简答题1、（ 8 分）写出以下复杂性函数的偏序关系（即依据渐进阶从低到高排序）：可编辑资料 - - - 欢迎下载精品名师归纳总结2n3nlognn .n lognn2n n103

8、可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结参考解答：103lognn lognn22n3nn.nn可编辑资料 - - - 欢迎下载精品名师归纳总结2、（8 分）现在有 8 位运动员要进行网球循环赛，要设计一个满意以下要求的竞赛日程表：（1） ）每个选手必

9、需与其他选手各赛一次。（2） ）每个选手一天只能赛一次。（3） ）循环赛一共进行n 1 天 。请利用分治法的思想，给这8 位运动员设计一个合理的竞赛日程。参考解答：12345678214365873412785643218765567812346587214378563412876543213、（8 分）某体育馆有一羽毛球场出租，现在总共有 10 位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示， si 表示开头租用时刻， fi 表示终止租用时刻， 10 个客户的申请如下表所示：123456789100315351188665498713121110i sifi同一时刻， 该羽毛球

10、场只能租借给一位客户，请设计一个租用支配方案， 在这 10 位客户里面，使得体育馆能尽可能满意多位客户的需求，并算出针对上表的 10 个客户申请，最多可以支配几位客户申请。参考解答： 将这 10 位客户的申请依据终止时间fi递增排序，如下表：123456789101305356881145678910111213i sifi挑选申请 1（1,4 ）依次检查后续客户申请，只要与已挑选的申请相容不冲突，就挑选该申请。直到全部申请检查完毕。申请4（ 5,7 ）、申请 8（ 8,11 ）、申请 10（ 11,13 ）最终，可以满意：申请 1（1,4 ）、申请 4（5,7 ）、申请 8（8,11 ）、申

11、请 10（ 11,13 ）共 4 个客户申请。这已经是可以满意的最大客户人数。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -4、（8 分）对于矩阵连乘所需最少数乘次数问题，其递归关系式为：可编辑资料 - - - 欢迎下载精品名师归纳总结m i,j min m i, k 0m k1, jijpp p ij可编辑资料 - - - 欢迎下载精品名师归纳总结i

12、 k ji 1kj可编辑资料 - - - 欢迎下载精品名师归纳总结其中 mi ， j 为运算矩阵连乘 Ai ,Aj 所需的最少数乘次数， pi-1 为矩阵 Ai 的行，pi 为矩阵 Ai 的列。现有四个矩阵，其中各矩阵维数分别为：A1A2A3A4501010 4040 3030 5p 0p 1p 1p 2p2p 3p 3p 4请依据以上的递归关系，运算出矩阵连乘积A1 A2A3 A4 所需要的最少数乘次数。参考解答：可编辑资料 - - - 欢迎下载精品名师归纳总结m11m24p0 p1 p4080005010510500可编辑资料 - - - 欢迎下载精品名师归纳总结m14minm12m13m

13、34m44p0 p2 p4 p0 p3 p420000600050405360002700005030534500可编辑资料 - - - 欢迎下载精品名师归纳总结105005、（8 分）有这样一类特别0-1 背包问题：可选物品 重量越轻的物品价值越高。n=6，c=20，P=（ 4， 8， 15，1，6，3），W=（ 5，3，2，10，4，8）。其中 n 为物品个数， c 为背包载重量， P 表示物品的价值， W表示物品的重量。请问对于此 0-1 背包问题， 应如何挑选放进去的物品， 才能使到放进背包的物品总价值最大，能获得的最大总价值多少？参考解答： 由于该 01 背包问题比较特别，恰好重量越

14、轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5 的三个物品放进背包，得到的价值和为15 + 8 + 6 + 4 = 33，为最大值。6. 请用英文写出三种以上能求解0-1 背包问题的设运算法策略。参考解答：Dynamic Programming BacktrackBranch-and-Bound（每答对一条给一分）7. 请说明动态规划方法为什么需要最优子结构性质。参考解答： 最优子结构性质是指大问题的最优解包含子问题的最优解。动态规划方法是自底向上运算各个子问题的最优解，即先运算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构

15、8. 请说明： 1 优先队列可用什么数据结构实现？2 优先队列插入算法基本思可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -想？ 3 优先队列插入算法时间复杂度？参考解答：（ 1）堆。 1 分（ 2）在小根堆中，将元素x 插入到堆的末尾，然后将元素 x 的关键字与其双亲的关键字比较，如元素 x 的关键字小于其双亲的关键字，就将元素 x 与其双亲交换，然后

16、再将元素 x 与其新双亲的关键字相比， 直到元素 x 的关键字大于双亲的关键字，或元素x 到根为止。 4 分（3）O log n（1 分）9.设计动态规划算法的主要步骤是怎么的？请简述。参考解答：（ 1）找出最优解的性质，并刻划其结构特点。6 分（ 2）递归的定义最优值。（ 3）以自底向上的方式运算出最优值。（4）依据运算最优值时得到的信息，构造最优解。10. 分治法所能解决的问题一般具有哪几个特点？请简述。参考解答：（ 1）该问题的规模缩小到肯定的程度就可以简洁的解决。6 分（ 2）该问题可以分解为如干个规模较小的相同问题，即该问题具有最优子结构性质 ;（3） 利用该问题分解出的子问题的解可

17、以合并为该问题的解。（ 4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。11. 分支限界法的搜寻策略是什么？参考解答： 在扩展结点处，先生成其全部的儿子结点（分支），然后再从当前的活结点表中挑选下一个扩展结点。为了有效的挑选下一扩展结点，加速搜寻的进程，在每一个活结点处，运算一个函数值（限界），并依据函数值，从当前活结点表中挑选一个最有利的结点作为扩展结点，使搜寻朝着解空间上有最优解的分支推动，以便尽快的找出一个最优解。6 分12 算法的要特性是什么？参考解答： 确定性、可实现性、输入、输出、有穷性13 算法分析的目的是什么？参考解答： 分析算法占用运算机资源的情形

18、，对算法做出比较和评判， 设计出额更好的算法。 14 算法的时间复杂性与问题的什么因素相关？参考解答： 算法的时间复杂性与问题的规模相关，是问题大小n 的函数。15 算法的渐进时间复杂性的含义？参考解答： 当问题的规模n 趋向无穷大时，影响算法效率的重要因素是Tn 的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用Tn 的数量级可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - -

19、- - - - - - - - 阶 评判算法。时间复杂度Tn 的数量级 阶 称为渐进时间复杂性。16 最坏情形下的时间复杂性和平均时间复杂性有什么不同？参考解答： 最坏情形下的时间复杂性和平均时间复杂性考察的是n 固定时， 不同输入实例下的算法所耗时间。 最坏情形下的时间复杂性取的输入实例中最大的时间复杂度：Wn = max Tn，I ,IDn平均时间复杂性是全部输入实例的处理时间与各自概率的乘积和：An = PITn，IIDn 17 简述二分检索（折半查找）算法的基本过程。参考解答：设输入是一个按非降次序排列的元素表Ai ：j和 x，选取 Ai+j/2与 x 比较，假如 Ai+j/2=x，就

20、返回 i+j/2，假如 Ai+j/2x，就 Ai ：i+j/2-1找 x，否就在 A i+j/2+1：j找 x。上述过程被反复递归调用。18 背包问题的目标函数和贪心算法最优化量度相同吗？参考解答： 不相同。目标函数：获得最大利润。最优量度：最大利润/ 重量比。 19 采纳回溯法求解的问题，其解如何表示？有什么规定？参考解答： 问题的解可以表示为n 元组：（x1,x 2, ,xn），xi Si , Si 为有穷集合，xi Si , （ x1 ,x 2, ,xn）具备完备性，即（ x1,x 2, ,xn）是合理的，就（x1,x 2 , ,xi ）in肯定合理。20 回溯法的搜寻特点是什么？参考解

21、答： 在解空间树上跳动式的深度优先搜寻，即用判定函数考察 xk 的取值，假如 xk 是合理的就搜寻 xk 为根节点的子树， 假如 xk 取完了全部的值， 便回溯到 xk-1 。21 n 皇后问题回溯算法的判别函数place 的基本流程是什么？参考解答： 将第 K 行的皇后分别与前k-1 行的皇后比较， 看是否与它们相容， 假如不相容就返回false ，测试完毕就返回true 。22 为什么用分治法设计的算法一般有递归调用？参考解答： 子问题的规模仍很大时，必需连续使用分治法，反复分治，必定要用到递归 .23 为什么要分析最坏情形下的算法时间复杂性？参考解答： 最坏情形下的时间复杂性打算算法的优

22、劣，并且最坏情形下的时间复杂性较平均时间复杂性游可操作性。24 简述渐进时间复杂性上界的定义。参考解答： Tn 是某算法的时间复杂性函数，fn是一简洁函数，存在正整数No和 C， nNo，有 Tnfn，这种关系记作Tn=Ofn。25 二分检索算法最多的比较次数？参考解答： 二分检索算法的最多的比较次数为log n。26 快速排序算法最坏情形下需要多少次比较运算？2参考解答： 最坏情形下快速排序退化成冒泡排序，需要比较n 次。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共 12 页 - - - - - - - - - -可

23、编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -27 贪心算法的基本思想？参考解答： 是一种依据最优化量度依次挑选输入的分级处理方法。基本思路是： 第一依据题意， 选取一种 量度标准。 然后按这种量度标准对这n 个输入排序， 依次挑选输入量加入部分解中。假如当前这个输入量的加入，不满意约束条件， 就不把此输入加到这部分解中28 回溯法的解（ x1,x 2 , ,xn）的模糊束一般指什么？参考解答： 回溯法的解（ x1,x 2, ,xn ）的模糊束一般指个元素之间应满意的某种关系。29 阐述归并排序的分治思路。参考解答： 讲

24、数组一分为二， 分别对每个集合单独排序， 然后将已排序的两个序列归并成一个含n 个元素的分好类的序列。 假如分割后子问题仍很大， 就连续分治，直到一个元素。30 快速排序的基本思想是什么。参考解答： 快速排序的基本思想是在待排序的N个记录中任意取一个记录， 把该记录放在最终位置后， 数据序列被此记录分成两部分。全部关键字比该记录关键字小的放在前一部分， 全部比它大的放置在后一部分，并把该记录排在这两部分的中间， 这个过程称作一次快速排序。之后重复上述过程， 直到每一部分内只有一个记录为止。31 什么是直接递归和间接递归？排除递归一般要用到什么数据结构？参考解答： 在定义一个过程或者函数的时候又

25、显现了调用本过程或者函数的成分，既调用它自己本身， 这称为直接递归。 假如过程或者函数P 调用过程或者函数 Q，Q又调用 P，这个称为间接递归。排除递归一般要用到栈这种数据结构。32 什么是哈密顿环问题？参考解答： 哈密顿环是指一条沿着图G的 N条边环行的路径， 它的拜访每个节点一次并且返回它的开头位置。33 用回溯法求解哈密顿环，如何定义判定函数？参 考 解 答 ： 当 前 选 择 的 节 点Xk是 从 未 到 过 的 节 点 , 即XkXii=1,2,k-1，且 CXk-1, Xk，假如 k=-1 ，就 CXk, X1。34 请写出 prim 算法的基本思想。参考解答： 思路是：最初生成树

26、 T 为空，依次向内加入与树有最小邻接边的 n-1 条边。处理过程：第一加入最小代价的一条边到 T，依据各节点到 T 的邻接边排序，挑选最小边加入，新边加入后，修改由于新边所转变的邻接边排序，再挑选下一条边加入，直至加入n-1 条边。三、算法设计题可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 7 页，共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -1. 【最长上升子序列问题】 （ 8 分） 提示：此题可采纳

27、动态规划算法实现可编辑资料 - - - 欢迎下载精品名师归纳总结对于给定的一个序列a1 , a2 , aN ， 1N1000 。我们可以得到一些递增可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结上升的子序列ai 1, ai 2 , aiK ，这里1i1i2i KN 。比如，对于序列 1,7,可编辑资料 - - - 欢迎下载精品名师归纳总结3, 5, 9, 4, 8，有它的一些上升子序列，如1, 7, 3, 4, 8等等。这些子序列中最长的长度是4，比如子序列 1, 3, 5, 8。你的任务：就是对于给定的序列，求出最长上升子序列的长度。 要求写

28、出你设计的算法思想及递推函数的公式表达。 .可编辑资料 - - - 欢迎下载精品名师归纳总结参考解答： 设f i 表示：从左向右扫描过来直到以ai 元素结尾的序列，获得的可编辑资料 - - - 欢迎下载精品名师归纳总结最长上升子序列的长度，且子序列包含a i 元素（ 1in ） 。可编辑资料 - - - 欢迎下载精品名师归纳总结f i max1f j 1: 当ai i a j;11jii1可编辑资料 - - - 欢迎下载精品名师归纳总结1i1;j 1ji , 都有 a i a j 可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结即， f(i) 是

29、从f 1，f 2, 到f i1 中找最大的一个值，再加1。或者可编辑资料 - - - 欢迎下载精品名师归纳总结就是 1。主要是看 ai 这个元素能否加入到之前已经获得的最长上升子序列， 假如能加入， 是之前已获得的最长上升子序列长度加一。 假如不能加入， 就取这最终一个元素作为一个单独子序列，长度为 1。最终，所要求的整个序列的最长公共子序列长度为maxfi: 1=i=当前最优解代价bestf ，就剪枝。 2 分（ 3）见（ 1）中所画的图。 5 分（ 4）最优解为 3 ，1，2 ，最优值为 25。3 分4. 【Gray 码构造问题】（8 分） 提示：此题可采纳分治递归算法实现可编辑资料 -

30、- - 欢迎下载精品名师归纳总结问题描述： “格雷码”是一个长度为2 n 的序列，满意：可编辑资料 - - - 欢迎下载精品名师归纳总结（a）每个元素都是长度为n 比特的串（b）序列中无相同元素（c）连续的两个元素恰好只有1 个比特不同例如： n=2 时，格雷码为 00 ，01，11， 10 。Gray 码是一种编码，这种编码可以防止在读取时，因各数据位时序上的差异造成的误读。 格雷码在工程上有广泛应用。但格雷码不便于运算， 请你设计一种构造方法，输入长度序列n，输出格雷码（你只要做出一种构造方案即可，格 雷码并不唯独）。参考解答： 此题可用分治法解决。当 n 1 时，输出格雷码 0, 1可编

31、辑资料 - - - 欢迎下载精品名师归纳总结当 n1 时，格雷码的长度为2 n ，即共有2 n 个码序列。此时，将问题一分为可编辑资料 - - - 欢迎下载精品名师归纳总结二，即上半部分和下半部分。上半部分最高位设为0，下半部分最高位设为1。剩下 n-1 位的格雷码的构造采纳递归的思路。评分准就：1) 答到使用分治算法，并且推导出分治算法的过程，边界设定清楚（即当仅输出 1 位的格雷码如何处理） ，此题即可得满分。2) 说明使用分治算法，但漏边界条件，扣2 分以上。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 10 页，共 12

32、页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -其它情形酌情考虑。5. （ 13 分）给定带权有向图（如下图所示）G =V,E ，其中每条边的权是非负实数。另外，仍给定 V 中的一个顶点，称为源。现在要运算从源到全部其它各顶点的最短路长度。这里路的长度是指路上各边权之和。现采纳Dijkstra算法运算从源顶点 1 到其它顶点间最短路径。请将此过程填入下表中。可编辑资料 - - - 欢迎下载精品名师归纳总结迭代S初始11234udist2dist3dist4dist5可编辑资料 -

33、 - - 欢迎下载精品名师归纳总结参考解答：（ 13 分）迭代Sudist2dist3dist4dist5初始1-103010011 ，2210603010021 ，2， 441050309031 ， 2，4， 331050306041 ， 2，3， 4，55105030606. （13 分 ） 有 0-1 背 包 问 题 如 下 ： n=6，c=20， P=（4，8，15，1，6，3），W=（5，3，2，10， 4， 8）。 其中 n 为物品个数， c 为背包载重量， P 表示物品的价值， W表示物品的重量。请问对于此0-1背包问题，应如何挑选放进去的物品，才能使到 放进背包的物品总价值最大

34、。P=15，8，6，4，3，1W=2，3，4，5，8，10 ，单位重量物品价值（7.5 ，2.67 ，1.5,0.8,0.375,0.1）参考解答：（ 13 分）可知随着物品的重量增加， 物品的价值削减。 因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。1. 先把重量为 2 的物品放进背包，此时剩余载重量为17，P 为 15。2. 把重量为 3 的物品放进背包，此时剩余载重量为14， P 为 23。3. 把重量为 4 的物品放进背包，此时剩余载重量为10， P 为 29。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 11 页，共 12 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -4. 把重量为 5 的物品放进背包，此时剩余载重量为5，P 为 33.由于 85，所以不能再放进背包。结果是