算法入门 - 贪心算法

一、贪心算法的概念

贪心算法是一种在每一步选择中都采取在当前看来是最优的选择，希望通过局部最优选择从而达到全局最优的算法策略。

二、贪心算法的基本思想

贪心算法总是做出在当前看来最好的选择，而不考虑整体的最优解。也就是说，它不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。

例如，在找零钱问题中，我们总是先选择面值最大的硬币进行找零，这就是一种贪心策略。

三、贪心算法的适用场景

贪心算法通常适用于具有最优子结构性质的问题，也就是说，一个问题的最优解包含其子问题的最优解。

但需要注意的是，贪心算法并非总是能得到全局最优解，在某些情况下，它可能会得到次优解。

四、贪心算法的实现步骤

1. 确定问题的最优子结构。
2. 设计贪心策略，即确定在每一步如何做出最优选择。
3. 证明贪心策略的正确性，或者通过实验验证其有效性。

算法入门 - 分治算法

一、分治算法的概念

分治算法是一种将复杂问题分解为若干个规模较小、相互独立，并且与原问题形式相同的子问题，然后分别求解子问题，最后将子问题的解合并得到原问题解的算法策略。

二、分治算法的基本思想

分治算法的基本思想是“分而治之”，即将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

三、分治算法的适用场景

分治算法适用于问题可以分解为若干个与原问题相似的子问题，并且这些子问题的解可以合并为原问题的解的情况。

例如，归并排序和快速排序就是典型的分治算法应用。

四、分治算法的实现步骤

1. 分解：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
2. 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。
3. 合并：将各个子问题的解合并为原问题的解。

贪心算法示例 - 找零钱问题

#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 本内容版权归梅耀元所有，未经授权请勿转载。

样例输入输出的格式改改

虽然很详细，但是本蒟蒻看不懂

额。。