算法图解（8~10贪心，动态规划，K最近邻算法）

本文主要是介绍算法图解（8~10贪心，动态规划，K最近邻算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

贪心算法

在每一步都选择局部最优解，从而期望最终得到全局最优解。

贪心算法并不总能保证全局最优解，因此需要满足以下两个条件：

1. 贪心选择性质：可以通过局部最优选择构造出全局最优解。
2. 最优子结构：问题的最优解包含其子问题的最优解。

实例：给定面额的硬币，用最少硬币凑出指定金额

int minCoins(vector<int>& coins, int amount) {int count = 0;for (int i = coins.size() - 1; i >= 0; --i) {count += amount / coins[i];amount %= coins[i];}return count;
}

NP完全问题

NP完全问题（NP-Complete Problem）是计算复杂性理论中的一个重要概念，它代表了一类特别难解决的问题。

P类问题:可以在多项式时间内由确定性算法解决。

NP类问题：这些问题的解可以在多项式时间内通过确定性算法验证，尽管找到解的过程可能非常困难。

以下是一些常见的NP完全问题：

• 旅行商问题（TSP）：给定一组城市和它们之间的距离，找到一条路径，使得旅行商访问每个城市一次且总路程最短。
• 顶点覆盖问题：在一个图中，选择最小数量的顶点，使得每条边至少有一个端点在这些顶点中。
• 3-SAT问题：给定一个布尔公式的CNF形式，判断是否存在一个真值赋值使得公式成立。
• 背包问题：给定一组物品，每个物品有一个价值和重量，选择其中一些物品使得总价值最大并且总重量不超过给定的限制。

解决NP完全问题的常用策略:

由于NP完全问题在一般情况下无法在多项式时间内求解，常用的策略包括：

• 近似算法：找到一个接近最优解的解。
• 启发式算法：如贪心算法、局部搜索等，虽然不能保证最优解，但通常能在合理时间内找到一个可行解。
• 分支定界法：在搜索解空间时，通过剪枝来减少计算量。
• 动态规划和分治法：在特定情况下，这些方法能有效地解决NP完全问题的某些

动态规划（Dynamic Programming, DP）

将一个复杂的问题分解为更简单的子问题，然后通过求解这些子问题来构建原问题的解。与贪心算法不同，动态规划不仅关注局部最优解，而是通过递归或迭代的方式求解全局最优解。

两个核心性质：最优子结构：重叠子问题

经典问题:

• 斐波那契数列：F(n)=F(n−1)+F(n−2),
• 背包问题:定一组物品，每个物品有重量和价值，求如何在不超过背包容量的情况下最大化总价值。
• 最长公共子序列（LCS）：给定两个序列，求它们的最长公共子序列长度。

实例：0/1 背包问题，循环前i个物品开始，容量为j时最大价值

int knapsack(int W, vector<int>& weights, vector<int>& values) {int n = weights.size();vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));for (int i = 1; i <= n; ++i) {for (int w = 0; w <= W; ++w) {if (weights[i - 1] <= w) {//《=当前的最大容量，可以选择添加物品dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);} else {dp[i][w] = dp[i - 1][w];}}}return dp[n][W];
}

实例LCS：第一个序列前i个字符与第二个序列前j个字符的LCS长度

int longestCommonSubsequence(const string& X, const string& Y) {int m = X.length();int n = Y.length();// 创建一个二维数组 dp[m+1][n+1]vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// 填充 dp 数组for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (X[i - 1] == Y[j - 1]) {//如果当前相等，就可以加入dp[i][j] = dp[i - 1][j - 1] + 1;} else {//否则，取上一次的最大值dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 返回 LCS 的长度return dp[m][n];
}

递归 VS DP

递归:

• 自顶向下：递归从原问题出发，逐步分解成更小的子问题，直到遇到基础情况，然后再返回并组合结果。
• 重复计算：在没有优化的情况下，递归会重复计算许多相同的子问题。例如，在求解斐波那契数列时，递归会多次计算相同的斐波那契值，导致指数级的时间复杂度。

动态规划:

• 记忆化递归（自顶向下DP）：在递归的基础上添加记忆化（也叫备忘录法），即将每个子问题的结果保存下来，当再次遇到相同子问题时直接返回保存的结果，避免了重复计算。

• 自底向上DP：动态规划还可以通过自底向上的方式，从最小的子问题开始逐步求解，直到得到原问题的解。这种方式通常使用表格或数组存储中间结果。

K最近邻算法

KNN是一种用于分类（编组）和回归（预测结果）的算法。通过比较样本之间的距离，找到距离目标样本最近的K个邻居，然后根据这些邻居的标签来进行分类。

优点：直观，应用于任意分布的数据，多类别分类问题

缺点：计算复杂度高：对样本的距离计算依赖

实例：用于机器学习领域

// 计算两个点之间的欧几里得距离
double euclideanDistance(vector<double>& point1, vector<double>& point2) {double sum = 0.0;for (int i = 0; i < point1.size(); ++i) {//测试点到所有点的距离和sum += pow(point1[i] - point2[i], 2);}return sqrt(sum);
}// KNN分类
int knnClassify(vector<vector<double>>& trainData, vector<int>& trainLabels, vector<double>& testData, int K) {vector<pair<double, int>> distances;  // 存储距离和对应的标签// 计算测试点到所有训练点的距离for (int i = 0; i < trainData.size(); ++i) {double dist = euclideanDistance(trainData[i], testData);distances.push_back({dist, trainLabels[i]});}// 按距离从小到大排序sort(distances.begin(), distances.end());// 投票决定类别vector<int> voteCount(10, 0);  // 假设标签的范围是0-9for (int i = 0; i < K; ++i) {voteCount[distances[i].second]++;}// 返回票数最多的类别return max_element(voteCount.begin(), voteCount.end()) - voteCount.begin();
}

这篇关于算法图解（8~10贪心，动态规划，K最近邻算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---