最优解问题

最优解问题"/>

最优解问题

最优解问题：在特定条件限制下，按特定需求得出最优结果

这类问题一般包含以下几种类型：

1. 最短路径（shortest path）
2. 游商问题（traveling salesperson problem TSP）
3. 装箱问题（bin packing）
4. 序列对比（DNA sequence alignment）
5. 背包问题（knapsacks）

遇到这种问题，我们常用的解法一般有以下几种：

• 贪婪算法（greedy algorithm）：在每一个步骤都最大化你的价值
• 穷举法（brute force）：罗列每一种可能的结果，再对比出最优解
• 动态规划（dynamic programming）：重叠子问题（overlapping sub problems），最优子结构(optimal substructure)，决策树（decision tree）：backtrack回溯，多项式算法（pseudo-polynomial algorithm）

第一种不一定能拿到最优解，第二种是指数级的复杂度，常用的是决策树方式去解决问题，其实决策树算是穷举的一种优化，因为它也需要列举出每一种可能，只是列举的过程中省略了很多不需要的步骤。
关于为何这类问题是指数级的，我们可以这么去分析，在背包问题中，任何一个物品都只有放和不放两种可能，如果把每个物品用一个bit位来表示，放入背包用1表示，不放用0表示，那么n个物体就可以用n个bit位来表示，如下：