发布时间 : 星期二 文章算法设计与分析习题 - 图文更新完毕开始阅读4a2af42ba300a6c30c229f7f
5、利用FIFO分支限界算法,给出下列0－1背包最优装载的求解步骤？
背包载重：M＝10； 物品重量：w1＝6、w2＝5、w3＝5； 物品价值：p1＝42、p2＝25、p3＝30
解：1)解空间：
2）求解过程：
第8章 NP完全性理论
1、什么是易解问题？什么是难解问题？难解问题分为哪两类？
答：1）易解问题：人们将存在多项式时间 算法的问题称为易解问题;
2）难解问题：将需要在指数时间内解决的问题称为难解问题；
3）难解问题有两类： 1）不可判定问题 2）非决定的难处理问题 。
2、什么是不可判定问题？什么是非决定的难处理问题？
答：1）不可判定问题 ：该类问题是不能解问题，它们太难了，以至于根本就不存在能求解它们的任何算法。
2）非决定的难处理问题： 这类问题是可判定的（即可解的）。 但是，这类问题即使使用非决定的计算机，也不能在多项式时间内求解它们。
3、什么是P类问题？什么是NP完全问题？
答：1）P类问题：是一类能够用确定性算法在多项式时间内求解的判断问题。事实上，所有易解问题都属于P类问题。
2）NP完全问题：对于某问题，很难找到其多项式时间的算法(或许根本不存在)，但是如果给了该问题的一个答案，则可以在多项式时间内判定或验证这个答案是否正确。 这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。
4、列出几个典型的NP完全问题？ 答：（1）图着色问题COLORING （2）路径问题LONG-PATH
（3）顶点覆盖问题VERTEX-COVER （4）子集和问题SUBSET-SUM
（5）哈密尔顿回路问题HAM-CYCLE （6）旅行商问题TSP
（7）装箱问题BIN-PACKING ， 能否用k个箱子来装n个物品；