求最值的方法
【导言】
在很多问题中，我们需要求最大值或最小值，比如优化问题、最优化问题或计算机视觉中的物体检测问题等。
而经典的求最值方法主要有枚举法、贪心算法、分治法、动态规划和深度优先搜索等。
本文将对这些方法进行详细的介绍，并结合实际例子进行说明。
【正文】
一、枚举法
枚举法是一种最基础的求最值方法。
它的求解思路是，对问题中所有可能的情况进行遍历，并得出最优解。
由于枚举法的过程中会穷尽所有情况，所以它具有很高的准确性。
但由于它的计算复杂度很高，因此只适用于问题空间较小的情况。
代码示例：
```
int maxSubArray(vector<int>& nums) {
int res = nums[0], sum = 0;
for (int i = 0; i < nums.size(); ++i) {
sum = max(sum + nums[i], nums[i]);
res = max(res, sum);
}
return res;
}
```
二、贪心算法
贪心算法是一种基于贪心策略的求最值方法。
贪心策略简单来说就是，每一步都选择当下最优的解。
贪心算法通常能够得到局部最优解，在一定条件下能够得到全局最优解。
由于它只考虑了当前的最优解，因此不能保证在所有情况下都能够得到最优解。
```
struct Item
{
int value;
int weight;
};
bool cmp(const Item &w1, const Item &w2)
{
double r1 = (double)w1.value / w1.weight;
double r2 = (double)w2.value / w2.weight;
return r1 > r2;
}
double fractionalKnapsack(int N, std::vector<Item> &items, int W)
{
std::sort(items.begin(), items.end(), cmp);
return res;
}
```
三、分治法
分治法是一种递归求解问题的方法。
它将问题分解成多个子问题，并递归地求解每个子问题，最后将子问题的解合并成原问题的解。
分治法通常用于具有重叠子问题和最优子结构性质的问题中。
double dist(Point p1, Point p2)
{
return sqrt((double)(p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
sort(px.begin(), px.end(), cmpX);
sort(py.begin(), py.end(), cmpY);
return closest(px, py, tmp, 0, n - 1);
}
int mid = (left + right) / 2;
Point midPoint = px[mid];
double d = min(dl, dr);
四、动态规划
动态规划是一种典型的求最值方法。
它通过将问题转换成子问题来求解，使用一个表格来存储已经计算过的中间状态，这样可以避免重复计算。
动态规划通常用于具有最优子结构和重叠子问题性质的问题中。
for (int i = 1; i < W.size() + 1; i++)
{
for (int j = 1; j < S + 1; j++)
{
if (W[i - 1] > j)
{
dp[i][j] = dp[i - 1][j];
}
else
{
dp[i][j] = max(dp[i - 1][j], V[i - 1] + dp[i - 1][j - W[i - 1]]);
}
}
}
五、深度优先搜索
深度优先搜索是一种通过对问题进行穷举来求解最优解的方法。
它通过搜索所有可能的路径来寻找最优解，一旦找到某个路径无法继续搜索，就回溯到之前的决策点上，尝试其他的决策。
深度优先搜索通常应用于具有无后效性质的问题中。
board[row][col] = 'Q';
backtrack(res, board, row + 1);
board[row][col] = '.';
}
}
【结论】除了上述的求最值方法外，还有一些扩展的方法可以对求解问题进行优化。
下面将介绍其中的两种：启发式搜索和近似算法。
一、启发式搜索
启发式搜索是一种启发式方法。
它结合了较好的搜索策略和高效的信息收集方法，通过对问题的剪枝优化，可以有效地提高求解问题的速度。
与深度优先搜索不同，启发式搜索不一定需要搜索全部的状态空间，而只需要搜索一部分具有较高概率的状态空间即可。
代码示例：
```
class Node
{
public:
vector<vector<int>> board;
int x, y;
int f, g, h;
Node(vector<vector<int>>& _board, int _x, int _y, int _step)
{
board = _board;
y = _y;
g = _step;
h = calculateH();
f =
g + h;
}
bool operator<(const Node& n) const
{
return f > n.f;
}
private:
int calculateH()
{
int res = 0;
int n = board.size();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] != 0)
{
int x = (board[i][j] - 1) / n; int y = (board[i][j] - 1) % n; res += abs(i - x) + abs(j - y); }
}
return res;
}
};
二、近似算法
近似算法是一种通过牺牲一定的问题精度来换取求解速度的方法。
它通过一些特殊的技术来对问题进行简化，从而提高问题的求解速度。
近似算法通常用于探索问题的可行解空间，它不保证求解的结果完全正确，但通常可以得到比较接近最优解的结果。
```
double stirling(int n)
{
return sqrt(2 * M_PI * n) * pow(double(n) / exp(1), n);
}
```
【结论】
启发式搜索和近似算法是两种常用的求最值方法。
启发式搜索通过搜索策略和信息收集技术，可以有效地优化问题求解过程，避免搜索无效状态，提高求解效率。
近似算法可以通过对问题进行简化，提高问题的求解速度，但往往不能保证得到最优解。
在实际应用中，可以根据问题的具体情况进行选择。
