制作百度移动网站,婚恋网站如何做自媒体营销,wordpress音乐门户主题,wordpress先登录再访问贪心算法简介
贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点#xff0c;做一个当时#xff08;看起来是#xff09;最佳的选择。这种启发式策略并不是总能产生出最优解#xff0c;但它常常能给出最优解。
在实际设计贪心算法时#xff0…贪心算法简介
贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点做一个当时看起来是最佳的选择。这种启发式策略并不是总能产生出最优解但它常常能给出最优解。
在实际设计贪心算法时通常直接做出贪心选择来构造子结构以产生一个待优化解决的子问题或者根据贪心选择来构造最优子结构。
贪心算法的一般做法
虽然贪心算法没有固定的解题模板但一般情况下使用贪心算法需要对问题进行分析可以参考下面的解题步骤 问题定义明确问题的输入、输出和目标。 状态定义**将问题分解为多个阶段每个阶段都有一个状态。**状态通常由问题的某些属性表示。如取最大值或者最小组等 确定贪心策略在每个阶段根据当前状态选择最优决策以期望达到全局最优解。这个最优决策通常是最优子结构的一部分问题的最优解可以通过其子问题的最优解来获得则问题具有最优子结构这意味着每个阶段的最优决策都是全局最优解的一部分。 代码实现根据上述步骤设计贪心算法编写代码。通常贪心算法包括一个循环每次循环中都选择当前最优决策并更新状态。 算法分析分析贪心算法的正确性和可行性。
贪心算法实例
下面演示的题目来自 洛谷P1080 国王游戏的题目, 其问题的求解的核心就是拆解问题将问题分为小问题并且取局部最优解。本题涉及的内容包括 贪心算法高精度的变换。
求解思路 代码
#includebits/stdc.h
using namespace std;
struct temp{int l,r,all;
}a[1005];
bool cmp(temp a,temp b){return a.allb.all;
}
int main(){int n;int result 0;cinn;for(int i0;in;i){cina[i].la[i].r;a[i].alla[i].l*a[i].r;}sort(a1,an1,cmp);int sum1;for(int i1;in;i){sum*a[i-1].l;if(sum/a[i].r result){result sum / a[i].r;}}coutresult;return 0;
}
测试情况如下所示可以看到在不考虑高精度的情况也是得分能达到60分故此在平时做题时当涉及到贪心算法的应用时需要将问题进行拆解细分为小问题并且运用数学逻辑将问题简答化建议采用假设方法。 正确AC解法 #include bits/stdc.h using namespace std;struct stu {int l; // 大臣的左手数int r; // 大臣的右手数} f[1005]; // 定义结构体数组 f最多可容纳 1005 位大臣// 比较函数用于排序bool cmp(stu a, stu b) {return a.l * a.r b.l * b.r; // 按左手数和右手数的乘积升序排序}int n; // 大臣数量vectorint ans(1, 0); // 初始化答案向量初始值为 0vectorint t(1, 1); // 初始化乘积向量初始值为 1// 高精度数乘法inline vectorint mul(vectorint a, int b) {vectorint res; // 存储结果的向量int t 0; // 进位int len a.size(); // 输入向量的长度for (int i 0; i len; i) {t a[i] * b; // 乘以 bres.push_back(t % 10); // 取当前位t / 10; // 更新进位}while (t) { // 处理剩余的进位res.push_back(t % 10);t / 10;}return res; // 返回乘法结果}// 高精度数除法inline vectorint div(vectorint a, int b) {vectorint res; // 存储结果的向量int r 0; // 余数int len a.size(); // 输入向量的长度for (int i len - 1; i 0; i--) { // 从低位到高位处理r 10 * r a[i]; // 将当前位加入余数if (r b) { // 如果余数大于等于除数res.push_back(r / b); // 计算商并存入结果r % b; // 更新余数} else {res.push_back(0); // 商为0}}vectorint cnt; // 存储结果的向量逆序len res.size();for (int i len - 1; i 0; i--) {cnt.push_back(res[i]); // 逆序存取结果}// 去掉前导零while ((cnt.back() 0) (cnt.size() 1)) {cnt.pop_back();}return cnt; // 返回除法结果}// 比较两个高精度数inline int compare(vectorint a, vectorint b) {int lenA a.size();int lenB b.size();if (lenA ! lenB) { // 长度不同return lenA - lenB; // 返回长度差} else { // 长度相同for (int i lenA - 1; i 0; i--) {if (a[i] ! b[i]) { // 从高位比较return a[i] - b[i]; // 返回差值}}return 0; // 相等}}int main() {cin n; // 输入大臣数量cin f[0].l f[0].r; // 输入国王的左手数和右手数for (int i 1; i n; i) { // 输入每位大臣的左右手数cin f[i].l f[i].r;}sort(f 1, f 1 n, cmp); // 按照比较函数排序大臣t mul(t, f[0].l); // 将国王的左手数乘入乘积for (int i 1; i n; i) { // 遍历每位大臣vectorint res div(t, f[i].r); // 计算当前大臣的金币数if (compare(ans, res) 0) { // 如果当前金币数更大ans res; // 更新结果}t mul(t, f[i].l); // 更新乘积乘入当前大臣的左手数}int len ans.size(); // 获取结果的长度for (int i len - 1; i 0; i--) { // 输出结果逆序cout ans[i];}cout endl; // 输出换行return 0; // 返回成功}
