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

2024-09-07 07:36
文章标签 算法 贪心 图解 动态 规划 最近

本文主要是介绍算法图解（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最近邻算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1144462。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
poj1330（LCA最近公共祖先）

poj1330（LCA最近公共祖先）

题意：求最近公共祖先 思路：之前学习了树链剖分，然后我就用树链剖分的一小部分知识就可以解这个题目了，记录每个结点的fa和depth。然后查找时，每次将depth大的结点往上走直到x = y。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>
阅读更多...
usaco 1.3 Barn Repair（贪心）

usaco 1.3 Barn Repair（贪心）

思路：用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序，选取最大的M-1个作为间隙，其余地方用木板盖住。 做法： 1.若，板（M） 的数目大于或等于 牛棚中有牛的数目（C），则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则，先对 牛牛们的门牌号排序，然后 用一个数组 blank[ ] 记录两门牌号之间的距离，然后 用数组 an
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2