一般网站建设的流程图,网站备案时长,公司向要做一个网站要怎么做,温岭专业营销型网站建设地址总有人在小白面前说#xff1a;我是搞算法的#xff0c;不是码农。又或者在想要进阶的时候#xff0c;有人问你#xff1a;你懂算法吗#xff1f;
所有#xff0c;算法到底是什么#xff1f;
从目的性来说#xff1a;它是计算方法#xff0c;用来达到自己目的的方式…总有人在小白面前说我是搞算法的不是码农。又或者在想要进阶的时候有人问你你懂算法吗
所有算法到底是什么
从目的性来说它是计算方法用来达到自己目的的方式。
直白的说算法 数学 逻辑 的计算机表达。还不够简单别急算法就是通过代码以除去穷举之外的编写逻辑去编写你的代码。
因为他所包含涉及到了很多计算机本行业之外的其他部分所以算法实际代表着隐形含义你有更广泛的知识面。这方面的展开不在此阐述。
让我们回归本次的主体贪婪算法。
贪心算法是一种基于贪心策略的算法它在每一步选择中都采取当前状态下最优的选择从而希望最终能够得到全局最优解。
注意这里是期望最优而非必定最优。也就是说存在期望落空的情况。而在这种情况下贪心算法并非最优解。 但是贪心他快啊。
下面是一个简单的贪心算法示例用于解决背包问题
#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; // 初始化当前背包重量为0double finalValue 0.0; // 初始化最终价值为0for (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; // 定义背包容量WItem arr[] {{60, 10}, {100, 20}, {120, 30}}; // 定义物品数组arrint 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函数来计算我们可以获得的最大价值。
