东营专业网站建设北京网站设计公司

开卷考试

1. 讲讲顺序算法中的分治法和回溯法的基本思想（20分）

2. （1）一个 0-1背包问题(即限定每种物品只能选择0个或1个，不能拆分)中，若各个物品按照重量递增顺序排列时，其价值正好按照递减序排列。对这个特殊的 0-1背包问题，设计一个算法，找出该问题的解。
   本题不限定方法。需要设计算法，需要给出复杂性分析。你可以选择完成可以展现你所设计算法优势的其它分析。（30分）

   （2）若上诉的01背包为超递增背包，即各个物品重量以超递增速度增加。设计多项式时间算法求解改背包问题，说明算法正确性，证明算法能求最优解（30分）

3. 证明3-SAT 问题可以多项式归结到MSP问题（25分）