贪心算法与动态规

一、引言

在算法设计中，贪心算法和动态规划是两种常用的优化技术，它们分别在不同类型的问题中提供高效的解决方案。两者在解决问题时都关注如何通过局部最优选择来达到全局最优，但其策略和适用场景有所不同。

二、贪心算法

2.1 贪心算法的基本概念

贪心算法（Greedy Algorithm）是一种在每个阶段选择局部最优解的算法。它的核心思想是“在当前状态下做出最好的选择”，并希望通过局部最优选择来推导出全局最优解。

贪心算法通常适用于问题有以下特点：

• 最优子结构：问题的最优解可以通过子问题的最优解来构造。
• 贪心选择性质：每次选择当前状态下的最优解，能够得到全局最优解。

2.2 贪心算法的基本步骤

1. 选择一个局部最优解：在当前阶段选择一个最优解。
2. 更新问题状态：通过局部最优解更新问题的状态。
3. 重复步骤1和2，直到问题的目标被解决。

2.3 贪心算法的典型问题

1. 活动选择问题：给定一系列活动，每个活动都有开始和结束时间，选择互不重叠的最大活动数。
2. 背包问题：对于给定的物品和背包的容量，如何选择物品放入背包，使得总价值最大（贪心法不一定能得到最优解，但在某些特定条件下能做到最优）。

2.4 活动选择问题（贪心法）

问题描述

给定一组活动的开始时间和结束时间，选择最大数量的互不重叠的活动。

算法思路

1. 按照活动的结束时间从小到大排序。
2. 选择第一个活动，然后从剩下的活动中选择与已选择活动互不重叠的下一个活动，直到选择完所有可能的活动。

代码示例：活动选择问题

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activity {
    int start, end;
};
bool compare(Activity a, Activity b) {
    return a.end < b.end;
}
int selectActivities(vector<Activity>& activities) {
    sort(activities.begin(), activities.end(), compare);
    int count = 1; // 至少选择第一个活动
    int lastEnd = activities[0].end;
    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].start >= lastEnd) { // 不重叠
            count++;
            lastEnd = activities[i].end;
        }
    }
    return count;
}
int main() {
    vector<Activity> activities = {{1, 3}, {2, 5}, {4, 6}, {7, 8}, {5, 7}};
    cout << "Maximum number of activities: " << selectActivities(activities) << endl;
    return 0;
}

2.5 贪心算法的优缺点

• 优点：通常实现简单，计算量较小。
• 缺点：无法保证全局最优解，贪心策略仅适用于特定的、满足贪心选择性质和最优子结构的场景。

三、动态规划

3.1 动态规划的基本概念

动态规划（Dynamic Programming，DP）是一种通过将问题分解为子问题，并存储其解以避免重复计算的算法。与贪心算法不同，动态规划通过考虑所有可能的选择来保证全局最优解。

动态规划通常适用于以下两种情况：

• 最优子结构：问题的最优解可以通过其子问题的最优解来构造。
• 重叠子问题：问题的解可以通过解决多个重叠的子问题来获得。

3.2 动态规划的基本步骤

1. 定义状态：确定问题的子结构，定义状态表示问题的规模。
2. 状态转移方程：通过递推公式或状态转移方程定义子问题之间的关系。
3. 初始条件：定义基本状态，通常是最小的子问题。
4. 计算结果：根据状态转移方程计算最终结果。

3.3 动态规划的典型问题

1. 斐波那契数列：计算斐波那契数列的第n项。
2. 背包问题：给定物品和背包的容量，如何选择物品放入背包，使得总价值最大。
3. 最短路径问题：如Dijkstra算法和Floyd算法。

3.4 0/1 背包问题（动态规划法）

问题描述

给定一组物品，每个物品有一个重量和价值，以及一个背包的容量，求在不超过背包容量的前提下，最大化背包的总价值。

算法思路

1. 状态定义：定义dp[i][w]表示前i个物品，背包容量为w时的最大价值。
2. 状态转移：对于每个物品，可以选择放入背包，也可以选择不放入背包。如果选择放入，则当前物品的重量需要不超过剩余容量。

代码示例：0/1 背包问题

#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int>& weights, vector<int>& values, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 1; 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];
}
int main() {
    vector<int> weights = {2, 3, 4, 5};
    vector<int> values = {3, 4, 5, 6};
    int W = 5; // 背包容量
    int n = weights.size();
    cout << "Maximum value in Knapsack = " << knapsack(W, weights, values, n) << endl;
    return 0;
}

3.5 动态规划的优缺点

• 优点：能保证全局最优解，适用于许多复杂的优化问题。
• 缺点：状态空间和时间复杂度通常较高，尤其是在状态空间较大的问题中，可能需要较大的内存和计算资源。

四、贪心算法与动态规划的比较

四.1 选择依据

• 贪心算法：适用于那些具有贪心选择性质且能够保证局部最优解能够得到全局最优解的问题。
• 动态规划：适用于有重叠子问题且能够通过子问题的最优解构造全局最优解的问题。

五、总结

• 贪心算法在某些问题中能提供快速的近似解，但不适用于所有问题。
• 动态规划能够处理更广泛的问题，并保证得到全局最优解，尤其适用于具有重叠子问题和最优子结构的问题。