贪心法
贪心法是一种解决最优化问题的算法思想。在贪心算法中，我们通常采用一种局部最优的策略来逐步构建全局最优解。在每一步中，我们考虑所有可行的决策，并选择可以最大化（或最小化）收益的决策。我们希望每次做出的局部最优决策能够最终导致全局最优解。
贪心算法通常适用于一些具有贪心选择性质的问题，即选择当前最优解可以得到全局最优解的问题。在这些问题中，贪心算法通常比其他算法更加高效，并且具有简单、直观、易于实现的特点。
贪心算法的基本思路如下：
定义问题的最优解结构，并利用贪心选择性质，设计出一个最优解的局部选择策略。
通过不断地做出局部最优选择，逐步构建出全局最优解。
证明局部最优选择策略可以导致全局最优解，即证明贪心选择性质成立。
贪心算法可以应用于许多不同的问题，包括最小生成树、最短路径、背包问题、调度问题等。但是，需要注意的是，贪心算法并不适用于所有的最优化问题。有些问题需要使用动态规划、回溯搜索等其他算法来求解。
下面是一个贪心算法的示例，用于解决经典的背包问题：
假设有一个容量为 W 的背包，有 n 个物品，每个物品有一个重量 wi 和一个价值 vi。现在我们需要选择一些物品放入背包中，使得它们的总重量不超过 W，且总价值最大。这是一个经典的优化问题，可以使用贪心算法来求解。
首先，我们可以将所有物品按照单位价值（即每单位重量的价值）从高到低排序。然后，从排好序的物品列表中逐个选取物品放入背包中，直到背包容量达到限制为止。在选择物品时，我们总是选择当前单位价值最高的物品。这样可以保证每次选择都是局部最优的，因为我们总是选择价值最高的物品放入背包中。最终，我们得到的背包内容就是全局最优解。
虽然贪心算法并不是所有问题的最优解算法，但在许多情况下，贪心算法可以通过简单、快速的方式找到局部最优解，从而得到接近全局最优解的结果。
下面给出一个贪心算法的经典示例：霍夫曼编码。
霍夫曼编码是一种可变长度编码，用于对字符进行压缩。在霍夫曼编码中，出现频率较高的字符使用较短的编码，而出现频率较低的字符使用较长的编码，从而达到压缩数据的目的。
霍夫曼编码的算法步骤如下：
统计每个字符在待压缩的数据中出现的频率，将它们按照频率从小到大排序。
构建一个霍夫曼树，其中每个叶子节点表示一个字符，其权值为该字符出现的频率。霍夫曼树的构建可以采用贪心算法。
具体地，从频率最小的两个字符开始，构建一个小根堆（或优先队列），每次取出两个权值最小的节点（即频率最小的两个字符），合并成一个新节点，权值为两个节点的权值之和，并将新节点插入小根堆中。重复执行上述过程，直到堆中只剩下一个节点，该节点即为霍夫曼树的根节点。
根据霍夫曼树为每个字符分配一个编码。具体地，从霍夫曼树的根节点开始遍历，每次向左走为 0，向右走为 1，遍历到一个叶子节点时，将该节点对应的字符的编码存储下来。
霍夫曼编码的优点在于，它可以根据数据中字符的出现频率，为不同的字符分配不同长度的编码，从而实现对数据的高效压缩。同时，由于霍夫曼编码的生成过程可以采用贪心算法，因此具有高效、简单、易于实现的特点。
然而，需要注意的是，由于霍夫曼编码的码长不固定，因此在编码和解码时需要额外的处理，否则可能会出现歧义或解码错误的情况。例如，当编码中的一个字符刚好是另一个字符编码的前缀时，可能会导致解码出现错误的情况。因此，在实际应用中需要注意这些问题。
下面我们用一个具体的例子来说明霍夫曼编码的过程。
假设我们有一个文本文件，其中包含以下 8 个字符及其出现频率：
| 字符 | 出现频率 |
|---|---|
| A | 45 |
| B | 13 |
| C | 12 |
| D | 16 |
| E | 9 |
| F | 5 |
| G | 8 |
| H | 4 |
我们需要对该文件进行压缩，可以采用霍夫曼编码。
首先，按照出现频率从小到大的顺序排序，得到以下表格：
| 字符 | 出现频率 |
|---|---|
| H | 4 |
| F | 5 |
| G | 8 |
| E | 9 |
| C | 12 |
| D | 16 |
| B | 13 |
| A | 45 |
接下来，我们用贪心算法构建霍夫曼树。具体地，我们首先将频率最小的两个字符 H 和 F 合并为一个节点，权值为 4+5=9，得到以下树：
9 / \\ H F
接着，我们将节点 G 和前面合并得到的节点合并，权值为 8+9=17，得到以下树：
17 / \\ 9 G / \\ H F
接着，我们将节点 E 和前面合并得到的节点合并，权值为 9+17=26，得到以下树：
26 / \\ / \\ / \\ 9 G / \\ H F / \\ E C
继续按照权值从小到大的顺序，将节点 D 和前面合并得到的节点合并，权值为 16+26=42，得到以下树：
42 / \\ / \\ / \\ 16 26 / \\ / \\ D 9 G / \\ / \\ C E H F
依次类推，最后得到完整的霍夫曼树：
133 / \\ / \\ / \\ / \\ / \\ / \\ 58 75 / \\ / \\ / \\ / \\ / \\ / \\ / \\ / \\ 25 33 37 38 / \\ / \\ / \\ / \\ A B C E G D F H
现在我们可以使用霍夫曼编码对文本进行压缩。对于每个字符，我们可以根据其在霍夫曼树中的路径得到对应的编码。具体地，从根节点开始，如果走左边的子节点，则在编码的末尾加上一个 0；如果走右边的子节点，则在编码的末尾加上一个 1。例如，字符 A 在霍夫曼树中的路径为左左左，对应的编码为 000。
对于上面的例子，字符的霍夫曼编码如下：
| 字符 | 频率 | 霍夫曼编码 |
|---|---|---|
| A | 45 | 0 |
| B | 13 | 101 |
| C | 12 | 100 |
| D | 16 | 111 |
| E | 9 | 1101 |
| F | 5 | 1100 |
| G | 8 | 1110 |
| H | 4 | 11001 |
由于霍夫曼编码是唯一的，因此我们可以根据上面的表格对文本进行解压缩。具体地，我们读入压缩后的二进制串，从根节点开始，如果当前二进制位为 0，则走左边的子节点；如果当前二进制位为 1，则走右边的子节点。如果到达了叶子节点，则输出对应的字符，并从根节点重新开始。例如，二进制串 1011100101 对应的文本为 BADE。
霍夫曼编码的时间复杂度为 O(nlogn)，其中 n 是字符集大小。
除了文本压缩外，霍夫曼编码还可以用于数据传输中的信道编码。在这种情况下，我们希望将原始数据编码成一个比特串，以便在传输过程中进行可靠的通信。霍夫曼编码可以根据不同字符出现的概率分配不同长度的编码，使得出现频率高的字符对应的编码比较短，从而在传输时占用的比特数更少，减少了传输时出错的可能性。
此外，霍夫曼编码还可以用于图像和音频的压缩，因为这些数据通常有较强的局部相关性。通过使用霍夫曼编码可以将这些相关性编码成较短的比特串，从而实现压缩效果。
不过需要注意的是，霍夫曼编码并不总是能够达到最优的压缩效果。例如，对于一个只包含两种字符的文本，如果它们的出现次数相等，那么使用霍夫曼编码得到的压缩效果与简单的替换压缩一样，没有任何优势。此外，由于霍夫曼编码需要统计字符出现的频率，因此对于一些流式数据，如网络数据流，它需要先对整个数据进行一次扫描，才能进行压缩，这样可能会导致一些延迟。针对这些问题，还可以使用其他的压缩算法，如LZ77和LZW等。
总的来说，霍夫曼编码是一种简单而高效的压缩算法，它广泛应用于数据压缩、通信和存储领域。
以下是一个使用贪心算法解决背包问题的C++代码示例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
int value;
int weight;
};
bool cmp(Item a, Item b) {
double r1 = (double)a.value / a.weight;
double r2 = (double)b.value / b.weight;
return r1 > r2;
}
double fractionalKnapsack(int W, vector<Item>& items) {
sort(items.begin(), items.end(), cmp);
int n = items.size();
int currWeight = 0;
double finalValue = 0.0;
for (int i = 0; i < n; i++) {
if (currWeight + items[i].weight <= W) {
currWeight += items[i].weight;
finalValue += items[i].value;
} else {
int remain = W - currWeight;
finalValue += items[i].value * ((double) remain / items[i].weight);
break;
}
}
return finalValue;
}
int main() {
int W = 50;
vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
double max_value = fractionalKnapsack(W, items);
cout << "Maximum value we can obtain = " << max_value << endl;
return 0;
}该程序演示了使用贪心算法解决分数背包问题。分数背包问题是指在背包容量有限的情况下，如何选取一些物品使得它们的总价值最大。与0/1背包问题不同的是，分数背包问题可以选择一部分物品的一部分，从而获得更多的价值。
在这个例子中，我们使用一个结构体Item来表示每个物品的价值和重量。我们定义一个比较函数cmp，它可以根据物品的单位重量价值从大到小排序。然后我们使用sort函数将所有物品按照这个顺序排序。
接着，我们使用一个循环来遍历所有物品。在每一步中，我们检查当前的背包容量是否足够放下当前物品，如果足够，我们将它放入背包，并将它的价值加到最终价值中。如果不足够，我们将它部分放入背包，并将它的价值按照比例加到最终价值中。最后，我们返回最终价值作为背包的最大价值。
运行该程序，输出结果为：
Maximum value we can obtain = 240
这意味着当背包容量为50时，我们可以选择第1个和第3个物品，使得它们的总价值为240，是所有可能的选择中最大的价值。
以下是另一个使用贪心算法解决任务调度问题的C++代码示例：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Task {
int start, finish;
};
bool cmp(Task a, Task b) {
return a.finish < b.finish;
}
int scheduleTasks(vector<Task>& tasks) {
sort(tasks.begin(), tasks.end(), cmp);
int n = tasks.size();
int prev_finish_time = 0;
int count = 0;
for (int i = 0; i < n; i++) {
if (tasks[i].start >= prev_finish_time) {
count++;
prev_finish_time = tasks[i].finish;
}
}
return count;
}
int main() {
vector<Task> tasks = {{1, 3}, {2, 5}, {3, 9}, {6, 8}};
int num_tasks = scheduleTasks(tasks);
cout << "Number of tasks scheduled: " << num_tasks << endl;
return 0;
}在这个例子中，我们使用一个结构体Task来表示每个任务的开始和结束时间。我们定义一个比较函数cmp，它可以根据任务的结束时间从小到大排序。然后我们使用sort函数将所有任务按照这个顺序排序。
接着，我们使用一个循环来遍历所有任务。在每一步中，我们检查当前任务的开始时间是否晚于上一个任务的结束时间，如果是，我们将当前任务计入最终的任务数中，并将当前任务的结束时间作为上一个任务的结束时间。否则，我们跳过当前任务。
最后，我们返回计数器count作为最终的任务数。
运行该程序，输出结果为：
Number of tasks scheduled: 3
这意味着在所有任务中，最多只能同时运行3个任务。我们可以选择第1个，第2个和第4个任务，它们不会发生时间冲突，所以它们可以同时运行。其他任务必须在它们之前或之后运行。
以下是使用贪心算法解决部分背包问题的C++代码示例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
int weight, value;
};
bool cmp(Item a, Item b) {
double ratio_a = (double) a.value / a.weight;
double ratio_b = (double) b.value / b.weight;
return ratio_a > ratio_b;
}
double fractionalKnapsack(vector<Item>& items, int capacity) {
sort(items.begin(), items.end(), cmp);
double value = 0.0;
int n = items.size();
for (int i = 0; i < n && capacity > 0; i++) {
if (items[i].weight <= capacity) {
value += items[i].value;
capacity -= items[i].weight;
} else {
value += ((double) items[i].value / items[i].weight) * capacity;
capacity = 0;
}
}
return value;
}
int main() {
vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};
int capacity = 50;
double max_value = fractionalKnapsack(items, capacity);
cout << "Maximum value: " << max_value << endl;
return 0;
}在这个例子中，我们使用一个结构体Item来表示每个物品的重量和价值。我们定义一个比较函数cmp，它可以根据物品的价值重量比从大到小排序。然后我们使用sort函数将所有物品按照这个顺序排序。
接着，我们使用一个循环来遍历所有物品。在每一步中，我们检查当前物品的重量是否小于等于当前背包容量。如果是，我们将当前物品放入背包中，并将当前背包容量减去该物品的重量。否则，我们只将部分该物品放入背包中，并将当前背包容量减去放入物品的重量。我们使用一个变量value来跟踪已经放入背包中的物品的总价值。
最后，我们返回变量value作为最大的物品总价值。
运行该程序，输出结果为：
Maximum value: 240
这意味着我们最多可以从所有物品中获得240单位的总价值，当我们使用部分背包策略将第1个和第2个物品放入背包时。第3个物品太重了，所以我们只能放入它的一部分。
以下是使用贪心算法解决活动安排问题的C++代码示例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activity {
int start, finish;
};
bool cmp(Activity a, Activity b) {
return a.finish < b.finish;
}
int maxActivities(vector<Activity>& activities) {
sort(activities.begin(), activities.end(), cmp);
int n = activities.size();
int count = 1;
int last_finish = activities[0].finish;
for (int i = 1; i < n; i++) {
if (activities[i].start >= last_finish) {
count++;
last_finish = activities[i].finish;
}
}
return count;
}
int main() {
vector<Activity> activities = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
int max_count = maxActivities(activities);
cout << "Maximum number of activities: " << max_count << endl;
return 0;
}在这个例子中，我们使用一个结构体Activity来表示每个活动的开始和结束时间。我们定义一个比较函数cmp，它可以根据活动的结束时间从小到大排序。然后我们使用sort函数将所有活动按照这个顺序排序。
接着，我们使用一个循环来遍历所有活动。我们使用一个变量count来记录当前已经安排的活动数，并使用一个变量last_finish来记录上一个安排的活动的结束时间。在每一步中，我们检查当前活动的开始时间是否大于等于上一个安排的活动的结束时间。如果是，我们将当前活动安排到日程中，并将计数器count加1，更新上一个活动的结束时间为当前活动的结束时间。否则，我们不安排当前活动。
最后，我们返回变量count作为最大安排的活动数。
运行该程序，输出结果为：
Maximum number of activities: 4
这意味着我们可以安排最多4个活动，并且可以是以下任意一组活动：{0, 6}, {1, 2}, {3, 4}, {5, 7}, {8, 9}。注意，还有另外一种可行的方案，包括活动{0, 6}，{6, 9}和{9, 10}，但它们的数量为3，而不是4。由于我们正在寻找最大数量的活动，因此我们选择了4个活动的方案。
下面再举一个贪心算法的例子，用于解决背包问题。
背包问题是一个经典的优化问题，它的目标是在给定的一组物品中选择一些物品放入一个背包中，使得所选物品的总价值最大，同时不能超过背包的容量。
以下是使用贪心算法解决背包问题的C++代码示例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
int value, weight;
};
bool cmp(Item a, Item b) {
return a.value * 1.0 / a.weight > b.value * 1.0 / b.weight;
}
double maxKnapsack(vector<Item>& items, int capacity) {
sort(items.begin(), items.end(), cmp);
double max_value = 0;
int n = items.size();
for (int i = 0; i < n; i++) {
if (capacity == 0) {
break;
}
if (items[i].weight <= capacity) {
max_value += items[i].value;
capacity -= items[i].weight;
} else {
max_value += items[i].value * 1.0 / items[i].weight * capacity;
capacity = 0;
}
}
return max_value;
}
int main() {
vector<Item> items = {{10, 2}, {5, 3}, {15, 5}, {7, 7}, {6, 1}, {18, 4}};
int capacity = 15;
double max_value = maxKnapsack(items, capacity);
cout << "Maximum value of knapsack: " << max_value << endl;
return 0;
}在这个例子中，我们使用一个结构体Item来表示每个物品的价值和重量。我们定义一个比较函数cmp，它可以根据每个物品的价值与重量的比值从大到小排序。然后我们使用sort函数将所有物品按照这个顺序排序。
接着，我们使用一个循环来遍历所有物品。我们使用一个变量max_value来记录当前已经选中的物品的总价值，并使用一个变量capacity来记录剩余的背包容量。在每一步中，我们检查当前物品的重量是否小于等于剩余的背包容量。如果是，我们将当前物品放入背包中，并将计数器max_value加上当前物品的价值，更新剩余的背包容量为原来的容量减去当前物品的重量。否则，我们只能将当前物品的一部分放入背包中，并更新计数器max_value和剩余的背包容量为当前物品价值与重量的比值乘以剩余容量。
最后，我们返回变量max_value作为背包可以达到的最大总价值。
运行该程序，输出结果为：
Maximum value of knapsack: 42.5
这意味着我们可以在背包中放在贪心算法中，通常需要证明贪心策略的正确性，即证明通过贪心选择可以获得全局最优解。一般来说，这需要满足贪心选择的局部最优解能够导致全局最优解。
