八股文-算法
1.利用动态规划计算以下矩阵连乘：A1(20* 25)、A2(25* 5)、A3(5* 15)、A4(15* 10)、A5(10* 20)、A6(20* 25)下列计算开销最小的是（ ）
A (A1A2A3)((A4A5)A6)
B (A1A2)((A3(A4A5))A6)
C (((A1((A2A3)A4)A5)A6)
D (A1A2)(((A3A4)A5)A6)
A的计算次数：
(A1A2A3)：25 * 20*5+20 * 5 *15=4000
((A4A5)A6)：15 * 10 * 20+15 * 20 * 25=10500
(A1A2A3)((A4A5)A6)：25* 20* 5+20* 5* 15+15* 10* 20+15* 20* 25+20* 15* 25=22000
2.贪心算法包含哪些
单源最短路径 最小生成树 0-1背包
3.线性规划问题又称线性规划，特指 目标函数 和 约束条件 皆为线性的 最优化问题
（1）关于线性规划描述不正确的是（ C ）。
图解法只能用于求解两个变量的线性规划问题
线性规划的最优解一定是可行解
线性规划标准形的决策变量不为零
线性规划可行域有界，则一定有最优解
（2）有关LP问题，（ A ）是错误的 。
当最优解多余一个时，最优解必有无穷多个
当有可行解时，必有最优解
当有最优解时，必有在可行集顶点达到的最优解
当有可行解时，必有可行基解
（3）关于标准形线性规划表述不正确的是（ B ）。
约束条件都为不等式
若存在最优解，则最优解必在可行域顶点上
若存在可行域，则可行域一定是凸集
可行域可以是无界
（4）下列不属于NP问题的是？
P问题： 如：排序问题。
一个问题可以在多项式（O(n^k)）的时间复杂度内解决。
NP问题： 如： 一个问题的解可以在多项式的时间内被验证。
NPH问题：
任意np问题都可以在多项式时间内归约为该问题，但该问题本身不一定是NP问题。归约的意思是为了解决问题A，先将问题A归约为另一个问题B，解决问题B同时也间接解决了问题A。
NPC问题：
既是NP问题，也是NP-hard问题。
如：
SAT问题
0-1整数规划
最大团
(SET PACKING)
最小点覆盖
集合覆盖
反馈节点集
反馈弧集
有向哈密尔顿回路
无向哈密尔顿回路
3SAT
图着色数
恰好覆盖
分团覆盖
(HITTING SET)
斯坦纳树
0-1背包
工作规划
最大割
5.下列描述不正确的是（ C ）。
所有NP问题都可以归约为NPC问题 NPC问题在多项式时间内找不到解 NPH问题在多项式时间内找不到解 P问题也是NP问题
PPTV工作强度 3人发布
