• 【算法与数据结构】--算法基础--算法设计与分析

    一、贪心算法

    贪心算法是一种解决优化问题的算法设计方法，其核心思想是在每一步选择当前状态下的最优解，从而希望最终达到全局最优解。下面将介绍贪心算法的原理、实现步骤，并提供C#和Java的实现示例。

    1.1 原理：

    贪心算法的原理基于局部最优选择，通过在每一步选择当前最优解，最终期望得到全局最优解。它不考虑过去的选择或未来的影响，仅关注眼前的局部最优决策。

    1.2 实现步骤：
    1. 问题建模：将问题抽象成一组选择和约束条件。
    2. 选择策略：确定每一步如何选择最优解。这需要根据问题特点来制定贪心策略。
    3. 检验可行性：检查当前选择是否满足问题的约束条件。
    4. 更新状态：根据选择更新问题的状态。
    5. 重复步骤2-4：迭代地选择最优解、检验可行性和更新状态，直到满足结束条件。
    1.3 C#实现示例：

    假设我们要解决背包问题，给定一组物品和背包容量，要求选择物品放入背包，使得总价值最大，且不超过背包容量。

    using System;
using System.Collections.Generic;

class GreedyAlgorithm
{
    public static List<Item> Knapsack(List<Item> items, int capacity)
    {
        items.Sort((a, b) => b.ValuePerWeight.CompareTo(a.ValuePerWeight));
        List<Item> selectedItems = new List<Item>();
        int currentWeight = 0;

        foreach (var item in items)
        {
            if (currentWeight + item.Weight <= capacity)
            {
                selectedItems.Add(item);
                currentWeight += item.Weight;
            }
        }

        return selectedItems;
    }
}

class Item
{
    public string Name { get; set; }
    public int Weight { get; set; }
    public int Value { get; set; }
    public double ValuePerWeight => (double)Value / Weight;
}

class Program
{
    static void Main()
    {
        List<Item> items = new List<Item>
        {
            new Item { Name = "Item1", Weight = 2, Value = 10 },
            new Item { Name = "Item2", Weight = 3, Value = 5 },
            new Item { Name = "Item3", Weight = 5, Value = 15 },
        };

        int capacity = 7;

        List<Item> selectedItems = GreedyAlgorithm.Knapsack(items, capacity);

        Console.WriteLine("Selected Items:");
        foreach (var item in selectedItems)
        {
            Console.WriteLine($"{item.Name} (Weight: {item.Weight}, Value: {item.Value})");
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    1.4 Java实现示例：

    同样以背包问题为例，以下是Java实现示例：

    import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class GreedyAlgorithm {
    public static List<Item> knapsack(List<Item> items, int capacity) {
        Collections.sort(items, Comparator.comparingDouble(Item::getValuePerWeight).reversed());
        List<Item> selectedItems = new ArrayList<>();
        int currentWeight = 0;

        for (Item item : items) {
            if (currentWeight + item.getWeight() <= capacity) {
                selectedItems.add(item);
                currentWeight += item.getWeight();
            }
        }

        return selectedItems;
    }
}

class Item {
    private String name;
    private int weight;
    private int value;

    public Item(String name, int weight, int value) {
        this.name = name;
        this.weight = weight;
        this.value = value;
    }

    public String getName() {
        return name;
    }

    public int getWeight() {
        return weight;
    }

    public int getValue() {
        return value;
    }

    public double getValuePerWeight() {
        return (double) value / weight;
    }
}

public class Main {
    public static void main(String[] args) {
        List<Item> items = new ArrayList<>();
        items.add(new Item("Item1", 2, 10));
        items.add(new Item("Item2", 3, 5));
        items.add(new Item("Item3", 5, 15));

        int capacity = 7;

        List<Item> selectedItems = GreedyAlgorithm.knapsack(items, capacity);

        System.out.println("Selected Items:");
        for (Item item : selectedItems) {
            System.out.println(item.getName() + " (Weight: " + item.getWeight() + ", Value: " + item.getValue() + ")");
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67

    上述示例演示了如何使用贪心算法解决背包问题，选择物品放入背包以使总价值最大。注意，贪心算法的适用性取决于问题的性质，不一定适用于所有优化问题。

    二、动态规划

    动态规划是一种用于解决优化问题的算法设计方法，它将问题分解成子问题，通过解决子问题来求解原始问题，以避免重复计算，提高效率。下面将介绍动态规划的原理、实现步骤，并提供C#和Java的实现示例。

    2.1 原理：

    动态规划的核心思想是利用已解决的子问题的解来构建原问题的解，从而减少重复计算。通常，动态规划问题满足两个条件：

    1. 最优子结构性质：问题的最优解可以通过子问题的最优解构建。
    2. 重叠子问题：问题可以被分解成许多重叠的子问题，每个子问题可以多次使用。
    2.2 实现步骤：
    1. 问题建模：将问题划分成子问题，定义子问题的状态和转移方程。
    2. 初始化：初始化边界条件，通常是最小规模子问题的解。
    3. 状态转移：根据子问题之间的关系，使用递归或迭代的方式计算子问题的解，并将结果保存在表格中。
    4. 解决原问题：通过解决子问题，逐步构建出原问题的最优解。
    5. 返回结果：返回原问题的最优解。
    2.3 C#实现示例：

    假设我们要解决经典的斐波那契数列问题，计算第n个斐波那契数。

    using System;

class DynamicProgramming
{
    public static long Fibonacci(int n)
    {
        if (n <= 1)
            return n;

        long[] fib = new long[n + 1];
        fib[0] = 0;
        fib[1] = 1;

        for (int i = 2; i <= n; i++)
        {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        return fib[n];
    }
}

class Program
{
    static void Main()
    {
        int n = 10;
        long result = DynamicProgramming.Fibonacci(n);
        Console.WriteLine($"Fibonacci({n}) = {result}");
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    2.4 Java实现示例：

    以下是Java实现示例：

    public class DynamicProgramming {
    public static long fibonacci(int n) {
        if (n <= 1)
            return n;

        long[] fib = new long[n + 1];
        fib[0] = 0;
        fib[1] = 1;

        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        return fib[n];
    }

    public static void main(String[] args) {
        int n = 10;
        long result = fibonacci(n);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    上述示例演示了如何使用动态规划计算斐波那契数列中第n个数的值。通过保存中间结果，避免了重复计算，提高了效率。动态规划可用于解决各种复杂问题，是一种重要的算法设计方法。

    三、分治算法

    分治算法（Divide and Conquer）是一种用于解决问题的算法设计方法，它将问题分解成子问题，解决子问题并合并子问题的解以得到原问题的解。下面将介绍分治算法的原理、实现步骤，并提供C#和Java的实现示例。

    3.1 原理：

    分治算法的核心思想是将问题分解成若干规模较小的子问题，分别解决这些子问题，然后将它们的解合并成原问题的解。通常，分治算法问题满足三个条件：

    1. 问题可以被分解成若干规模较小的相同子问题。
    2. 子问题的解可以通过递归方式获得。
    3. 可以将子问题的解合并成原问题的解。
    3.2 实现步骤：
    1. 问题建模：将原问题划分成若干子问题，定义子问题的状态和递归关系。
    2. 递归求解：递归地求解子问题，直到问题规模足够小，可以直接解决。
    3. 合并子问题的解：将子问题的解合并成原问题的解。
    4. 返回结果：返回原问题的解。
    3.3 C#实现示例：

    假设我们要解决归并排序问题，对一个整数数组进行排序。

    using System;

class DivideAndConquer
{
    public static void MergeSort(int[] arr)
    {
        if (arr.Length <= 1)
            return;

        int mid = arr.Length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.Length - mid];

        for (int i = 0; i < mid; i++)
            left[i] = arr[i];

        for (int i = mid; i < arr.Length; i++)
            right[i - mid] = arr[i];

        MergeSort(left);
        MergeSort(right);

        Merge(arr, left, right);
    }

    private static void Merge(int[] arr, int[] left, int[] right)
    {
        int i = 0, j = 0, k = 0;

        while (i < left.Length && j < right.Length)
        {
            if (left[i] < right[j])
                arr[k++] = left[i++];
            else
                arr[k++] = right[j++];
        }

        while (i < left.Length)
            arr[k++] = left[i++];

        while (j < right.Length)
            arr[k++] = right[j++];
    }
}

class Program
{
    static void Main()
    {
        int[] arr = { 12, 11, 13, 5, 6, 7 };
        DivideAndConquer.MergeSort(arr);

        Console.WriteLine("Sorted array:");
        foreach (var num in arr)
        {
            Console.Write(num + " ");
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    3.4 Java实现示例：

    以下是Java实现示例：

    public class DivideAndConquer {
    public static void mergeSort(int[] arr) {
        if (arr.length <= 1)
            return;

        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];

        System.arraycopy(arr, 0, left, 0, mid);
        System.arraycopy(arr, mid, right, 0, arr.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(arr, left, right);
    }

    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] < right[j])
                arr[k++] = left[i++];
            else
                arr[k++] = right[j++];
        }

        while (i < left.length)
            arr[k++] = left[i++];

        while (j < right.length)
            arr[k++] = right[j++];
    }

    public static void main(String[] args) {
        int[] arr = { 12, 11, 13, 5, 6, 7 };
        mergeSort(arr);

        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    上述示例演示了如何使用分治算法进行归并排序，将一个整数数组进行排序。通过将问题分解成子问题，然后合并子问题的解，实现了高效的排序算法。分治算法可用于解决各种复杂问题，是一种重要的算法设计方法。

    四、回溯算法

    回溯算法（Backtracking）是一种用于解决组合问题和搜索问题的算法设计方法，它通过不断尝试各种可能性来逐步构建解决方案，并在遇到无法继续或不符合条件的情况下回溯到上一步重新选择。下面将介绍回溯算法的原理、实现步骤，并提供C#和Java的实现示例。

    4.1 原理：

    回溯算法的核心思想是深度优先搜索，它通过递归或迭代方式探索问题的解空间树。在搜索过程中，如果发现当前路径无法满足问题的要求，就回溯到上一步，尝试其他可能性，直到找到问题的解或确定无解。回溯算法通常适用于以下类型的问题：

    1. 组合问题：从一组元素中选择一些元素形成组合，如排列、子集、组合总和等问题。
    2. 搜索问题：在状态空间中搜索解，如八皇后问题、数独、迷宫问题等。
    4.2 实现步骤：
    1. 问题建模：将问题抽象成一个状态空间树，定义问题的状态、选择、约束条件和目标。
    2. 选择路径：从当前状态出发，选择一条路径前进，尝试一个可能的选择。
    3. 递归或迭代：根据选择，递归或迭代地进入下一层状态，继续选择路径。
    4. 检查条件：在每一步检查是否满足问题的约束条件，如果不满足，回溯到上一步。
    5. 找到解或无解：如果找到问题的解，记录解或处理解；如果无法继续或已探索完所有可能性，则回溯到上一步。
    6. 返回结果：返回最终的解或处理结果。
    4.3 C#实现示例：

    假设我们要解决组合总和问题，找到数组中所有可能的组合，使其和等于目标值。

    using System;
using System.Collections.Generic;

class Backtracking
{
    public static IList<IList<int>> CombinationSum(int[] candidates, int target)
    {
        IList<IList<int>> result = new List<IList<int>>();
        List<int> current = new List<int>();
        CombinationSumHelper(candidates, target, 0, current, result);
        return result;
    }

    private static void CombinationSumHelper(int[] candidates, int target, int start, List<int> current, IList<IList<int>> result)
    {
        if (target == 0)
        {
            result.Add(new List<int>(current));
            return;
        }

        for (int i = start; i < candidates.Length; i++)
        {
            if (target - candidates[i] >= 0)
            {
                current.Add(candidates[i]);
                CombinationSumHelper(candidates, target - candidates[i], i, current, result);
                current.RemoveAt(current.Count - 1);
            }
        }
    }
}

class Program
{
    static void Main()
    {
        int[] candidates = { 2, 3, 6, 7 };
        int target = 7;
        IList<IList<int>> result = Backtracking.CombinationSum(candidates, target);

        Console.WriteLine("Combination Sum:");
        foreach (var list in result)
        {
            Console.WriteLine(string.Join(", ", list));
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    4.4 Java实现示例：

    以下是Java实现示例：

    import java.util.ArrayList;
import java.util.List;

public class Backtracking {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        combinationSumHelper(candidates, target, 0, current, result);
        return result;
    }

    private static void combinationSumHelper(int[] candidates, int target, int start, List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (target - candidates[i] >= 0) {
                current.add(candidates[i]);
                combinationSumHelper(candidates, target - candidates[i], i, current, result);
                current.remove(current.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] candidates = { 2, 3, 6, 7 };
        int target = 7;
        List<List<Integer>> result = combinationSum(candidates, target);

        System.out.println("Combination Sum:");
        for (List<Integer> list : result) {
            System.out.println(list);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    上述示例演示了如何使用回溯算法解决组合总和问题，找到数组中所有可能的组合，使其和等于目标值。通过不断选择路径和回溯，可以找到所有解。回溯算法是解决组合和搜索问题的强大工具。

    五、总结

    贪心算法是一种解决优化问题的方法，通过每一步选择当前最优解，期望达到全局最优解。动态规划将问题分解成子问题，通过解决子问题来求解原问题，以避免重复计算。分治算法将问题分解成子问题，解决子问题并合并子问题的解以得到原问题的解。回溯算法通过不断尝试各种可能性来逐步构建解决方案，适用于组合和搜索问题。这些算法都有不同的应用领域和实现步骤，可根据问题特点选择合适的算法。

  • 相关阅读:
    使用webpack-bundle-analyzer分析uni-app 的微信小程序包大小（HbuilderX运行）
    Charles 乱码解决办法
    【经典算法学习-排序篇】冒泡排序
    Numpy入门[17]——数组广播机制
    Spring的简单使用（3）
    芯片启动以及boot
    Python快速刷题网站——牛客网 数据分析篇（十一）
    卡片布局以及鼠标悬浮展示全部
    2-1-1.spring源码--BeanFactory
    SLAM ORB-SLAM2（6）系统对象
  • 原文地址：https://blog.csdn.net/gangzhucoll/article/details/133757602