总有人在小白面前说：我是搞算法的，不是码农。又或者在想要进阶的时候，有人问你：你懂算法吗？
所有，算法到底是什么？
从目的性来说：它是计算方法，用来达到自己目的的方式。
直白的说：算法 = 数学 + 逻辑 的计算机表达。还不够简单？别急，算法就是通过代码以除去穷举之外的编写逻辑去编写你的代码。
因为他所包含涉及到了很多计算机本行业之外的其他部分，所以算法实际代表着隐形含义：你有更广泛的知识面。这方面的展开不在此阐述。
让我们回归本次的主体：贪婪算法。
贪心算法是一种基于贪心策略的算法，它在每一步选择中都采取当前状态下最优的选择，从而希望最终能够得到全局最优解。
注意：这里是期望最优，而非必定最优。也就是说存在期望落空的情况。而在这种情况下，贪心算法，并非最优解。
但是，贪心，他快啊。
下面是一个简单的贪心算法示例，用于解决背包问题：
#include <iostream> // 引入iostream库，用于输入输出 #include <algorithm> // 引入algorithm库，用于排序 using namespace std; // 使用std命名空间 struct Item { // 定义一个结构体Item，包含每个物品的价值和重量 int value; int weight; }; bool cmp(Item a, Item b) { // 定义一个比较函数cmp，用于比较每个物品的价值和重量比率 double r1 = (double)a.value / a.weight; // 计算物品a的价值和重量比率 double r2 = (double)b.value / b.weight; // 计算物品b的价值和重量比率 return r1 > r2; // 返回比率较大的物品 } double fractionalKnapsack(int W, Item arr[], int n) { // 定义一个函数fractionalKnapsack，用于解决背包问题 sort(arr, arr + n, cmp); // 对物品按照价值和重量比率进行排序 int curWeight = 0; // 初始化当前背包重量为0 double finalValue = 0.0; // 初始化最终价值为0 for (int i = 0; i < n; i++) { // 遍历每个物品 if (curWeight + arr[i].weight <= W) { // 如果当前背包重量加上物品重量小于等于背包容量 curWeight += arr[i].weight; // 将物品放入背包中 finalValue += arr[i].value; // 增加最终价值 } else { // 如果当前背包重量加上物品重量大于背包容量 int remain = W - curWeight; // 计算剩余空间 finalValue += arr[i].value * ((double) remain / arr[i].weight); // 将物品分成一部分放入背包中 break; // 结束循环 } } return finalValue; // 返回最终价值 } int main() { // 主函数 int W = 50; // 定义背包容量W Item arr[] = {{60, 10}, {100, 20}, {120, 30}}; // 定义物品数组arr int n = sizeof(arr) / sizeof(arr[0]); // 计算物品数量 cout << "Maximum value we can obtain = " // 输出提示信息 << fractionalKnapsack(W, arr, n); // 调用fractionalKnapsack函数计算最大价值并输出 return 0; // 返回0表示程序正常结束 }
在这个示例中，我们定义了一个Item结构体，其中包含每个物品的价值和重量。我们还定义了一个cmp函数，用于比较每个物品的价值和重量比率，以便在排序时使用。
fractionalKnapsack函数是我们的贪心算法实现。我们首先按照价值和重量比率对物品进行排序，然后从最高比率的物品开始，将尽可能多的物品放入背包中，直到背包装满为止。如果我们无法将整个物品放入背包中，则将其分成一部分，并将其放入背包中。
在main函数中，我们定义了一个背包容量W和一组物品，然后调用fractionalKnapsack函数来计算我们可以获得的最大价值。
