阿巴阿巴，咋讲啊，这样的话太不详细了，就这样吧！
算法入门 - 贪心算法
一、贪心算法的概念
贪心算法是一种在每一步选择中都采取在当前看来是最优的选择，希望通过局部最优选择从而达到全局最优的算法策略。
二、贪心算法的基本思想
贪心算法总是做出在当前看来最好的选择，而不考虑整体的最优解。也就是说，它不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
例如，在找零钱问题中，我们总是先选择面值最大的硬币进行找零，这就是一种贪心策略。
三、贪心算法的适用场景
贪心算法通常适用于具有最优子结构性质的问题，也就是说，一个问题的最优解包含其子问题的最优解。
但需要注意的是，贪心算法并非总是能得到全局最优解，在某些情况下，它可能会得到次优解。
四、贪心算法的实现步骤
- 确定问题的最优子结构。
- 设计贪心策略，即确定在每一步如何做出最优选择。
- 证明贪心策略的正确性，或者通过实验验证其有效性。
算法入门 - 分治算法
一、分治算法的概念
分治算法是一种将复杂问题分解为若干个规模较小、相互独立，并且与原问题形式相同的子问题，然后分别求解子问题，最后将子问题的解合并得到原问题解的算法策略。
二、分治算法的基本思想
分治算法的基本思想是“分而治之”，即将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
三、分治算法的适用场景
分治算法适用于问题可以分解为若干个与原问题相似的子问题，并且这些子问题的解可以合并为原问题的解的情况。
例如，归并排序和快速排序就是典型的分治算法应用。
四、分治算法的实现步骤
- 分解：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
- 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。
- 合并：将各个子问题的解合并为原问题的解。
贪心算法示例 - 找零钱问题
#include <iostream>
#include <vector>
using namespace std;
vector<int> greedyChange(int amount) {
vector<int> coins = {25, 10, 5, 1};
vector<int> result;
for (int coin : coins) {
while (amount >= coin) {
amount -= coin;
result.push_back(coin);
}
}
return result;
}
int main() {
int amount = 67;
vector<int> change = greedyChange(amount);
for (int coin : change) {
cout << coin << " ";
}
cout << endl;
return 0;
}
分治算法示例 - 归并排序
#include <iostream>
#include <vector>
using namespace std;
// 合并两个已排序的子数组为一个排序数组
void merge(vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
}
// 归并排序函数
void mergeSort(vector<int>& arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// 打印数组函数
void printArray(const vector<int>& arr) {
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}
// 测试示例
int main() {
vector<int> arr = {12, 11, 13, 5, 6};
int arr_size = arr.size();
cout << "给定数组为 ";
printArray(arr);
mergeSort(arr, 0, arr_size - 1);
cout << "排序后的数组为 ";
printArray(arr);
return 0;
}
自编题(较难)
贪心算法题目：
在一个城市中，有若干个公交站点，每个站点都有特定的乘客数量等待上车。同时，有多种型号的公交车可供调度，每种型号的公交车有不同的载客量和运营成本。调度中心需要在一天内安排公交车的运营路线，以尽可能满足乘客需求的同时最小化运营成本。假设公交车在每个站点都必须停靠，且一旦出发就不能更改路线。
输入：站点数量 N，各站点乘客数量 num1, num2,…, numN，公交车型号数量 M，各型号公交车载客量 cap1, cap2,…, capM，各型号公交车运营成本 cost1, cost2,…, costM
输入示例：3 30 20 40 2 50 30 100 80
输出：选择的公交车型号及对应的路线
输出示例：A 1 2 3 B 2
时间限制：500 毫秒
空间限制：512MB
分治算法题目：
给定一个二维矩阵，其中每个元素都是整数。要求找出矩阵中的一个子矩阵，使得子矩阵中所有元素的和最大。
输入：矩阵行数 R，矩阵列数 C，矩阵元素值 mat[1][1], mat[1][2],…, mat[R][C]
输入示例：3 3 1 2 -3 4 5 6 7 8 9
输出：最大子矩阵左上角坐标(x1, y1)，右下角坐标(x2, y2)，和 sum
输出示例：1 1 3 3 45
时间限制：1000 毫秒
空间限制：1GB
(有问题的话请大佬告知我)
(内心：我想要勋章(っ °Д °;)っ) (第三天)
© 2024 本内容版权归梅耀元所有，未经授权请勿转载。