网站建设管理策划书,延安免费做网站公司,平凉建设局官方网站,静态网站特点贪心算法#xff1a;基础入门篇 文章目录#xff1a; 贪心算法#xff1a;基础入门篇一、认识贪心算法二、常见贪心问题2.1 纸牌问题2.2 背包问题#xff08;基础版#xff09;2.3 简单数学证明问题 三、总结 一、认识贪心算法
在求最优解的问题中#xff0c;以某种贪心…贪心算法基础入门篇 文章目录 贪心算法基础入门篇一、认识贪心算法二、常见贪心问题2.1 纸牌问题2.2 背包问题基础版2.3 简单数学证明问题 三、总结 一、认识贪心算法
在求最优解的问题中以某种贪心标准从状态的最初始找到每一步最优解通过多次的贪心求解最终得到整个问题的最优解此种解题的方法为贪心算法。可见贪心算法并不是一种固定的算法而是根据问题的条件而产生的一种解决问题的思维模式。
由定义可知贪心算法是由局部的最优解得到总体的最优解因此在使用贪心算法之前要先判断问题是否适合使用贪心算法。
二、常见贪心问题
2.1 纸牌问题
纸牌问题是最简单也最好理解的贪心问题题目如下 题目描述:
有 N N N 堆纸牌编号分别为 1 , 2 , … , N 1,2,\ldots,N 1,2,…,N。每堆上有若干张但纸牌总数必为 N N N 的倍数。可以在任一堆上取若干张纸牌然后移动。
移牌规则为在编号为 1 1 1 堆上取的纸牌只能移到编号为 2 2 2 的堆上在编号为 N N N 的堆上取的纸牌只能移到编号为 N − 1 N-1 N−1 的堆上其他堆上取的纸牌可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法用最少的移动次数使每堆上纸牌数都一样多。
例如 N 4 N4 N4 时 4 4 4 堆纸牌数分别为 9 , 8 , 17 , 6 9,8,17,6 9,8,17,6。
移动 3 3 3 次可达到目的
从第三堆取 4 4 4 张牌放到第四堆此时每堆纸牌数分别为 9 , 8 , 13 , 10 9,8,13,10 9,8,13,10。从第三堆取 3 3 3 张牌放到第二堆此时每堆纸牌数分别为 9 , 11 , 10 , 10 9,11,10,10 9,11,10,10。从第二堆取 1 1 1 张牌放到第一堆此时每堆纸牌数分别为 10 , 10 , 10 , 10 10,10,10,10 10,10,10,10。
输入格式:
第一行共一个整数 N N N表示纸牌堆数。 第二行共 N N N 个整数 A 1 , A 2 , … , A N A_1,A_2,\ldots,A_N A1,A2,…,AN表示每堆纸牌初始时的纸牌数。
输出格式:
共一行即所有堆均达到相等时的最少移动次数。
样例
样例输入
4
9 8 17 6样例输出
3提示
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 100 1 \le N \le 100 1≤N≤100 1 ≤ A i ≤ 10000 1 \le A_i \le 10000 1≤Ai≤10000。
【题目来源】
NOIP 2002 提高组第一题 题目解析
根据移牌规则可以得出以下通式 { a [ i ] a v e , a [ i 1 ] ( a [ i ] − a v e ) a [ i 1 ] a [ i ] a v e a [ i ] a v e , a [ i 1 ] a [ i 1 ] − ( a v e − a [ i ] ) \left\{\begin{matrix}a[i] ave,a[i1](a[i]-ave)a[i1]\\a[i]ave \\a[i] ave,a[i1]a[i1]-(ave-a[i])\end{matrix}\right. ⎩ ⎨ ⎧a[i]ave,a[i1](a[i]−ave)a[i1]a[i]avea[i]ave,a[i1]a[i1]−(ave−a[i]) 在左至右开始排列的情况下从移牌规则中可得知大于平均数的牌只能向左移动反之小于平均数的牌只能向右移动。由此可以画出以下关系图 #mermaid-svg-KW6IHnaQsmtHYw7C {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-KW6IHnaQsmtHYw7C .error-icon{fill:#552222;}#mermaid-svg-KW6IHnaQsmtHYw7C .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-KW6IHnaQsmtHYw7C .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-KW6IHnaQsmtHYw7C .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-KW6IHnaQsmtHYw7C .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-KW6IHnaQsmtHYw7C .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-KW6IHnaQsmtHYw7C .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-KW6IHnaQsmtHYw7C .marker{fill:#333333;stroke:#333333;}#mermaid-svg-KW6IHnaQsmtHYw7C .marker.cross{stroke:#333333;}#mermaid-svg-KW6IHnaQsmtHYw7C svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-KW6IHnaQsmtHYw7C .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-KW6IHnaQsmtHYw7C .cluster-label text{fill:#333;}#mermaid-svg-KW6IHnaQsmtHYw7C .cluster-label span{color:#333;}#mermaid-svg-KW6IHnaQsmtHYw7C .label text,#mermaid-svg-KW6IHnaQsmtHYw7C span{fill:#333;color:#333;}#mermaid-svg-KW6IHnaQsmtHYw7C .node rect,#mermaid-svg-KW6IHnaQsmtHYw7C .node circle,#mermaid-svg-KW6IHnaQsmtHYw7C .node ellipse,#mermaid-svg-KW6IHnaQsmtHYw7C .node polygon,#mermaid-svg-KW6IHnaQsmtHYw7C .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-KW6IHnaQsmtHYw7C .node .label{text-align:center;}#mermaid-svg-KW6IHnaQsmtHYw7C .node.clickable{cursor:pointer;}#mermaid-svg-KW6IHnaQsmtHYw7C .arrowheadPath{fill:#333333;}#mermaid-svg-KW6IHnaQsmtHYw7C .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-KW6IHnaQsmtHYw7C .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-KW6IHnaQsmtHYw7C .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-KW6IHnaQsmtHYw7C .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-KW6IHnaQsmtHYw7C .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-KW6IHnaQsmtHYw7C .cluster text{fill:#333;}#mermaid-svg-KW6IHnaQsmtHYw7C .cluster span{color:#333;}#mermaid-svg-KW6IHnaQsmtHYw7C div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-KW6IHnaQsmtHYw7C :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 移动 移动 移动 移动 第一堆 第二堆 第N堆 根据上述思路即可写出相应代码
#include iostream
using namespace std;
int main(){int a,sum0,ave0;int b[100];cina;for(int i0;ia;i){cinb[i];aveb[i];}aveave/a;for(int i0;ia;i){if(b[i]ave){b[i1]b[i]-ave;sum;}if(aveb[i]){b[i1]b[i1]-(ave-b[i]);sum;}}coutsum;return 0;
}2.2 背包问题基础版
背包问题是贪心算法中比较经典的贪心问题同时背包问题也是一个经典的动态规划问题其基本形式是给定一个背包容量为C和一组物品每个物品有自己的重量和价值现在从这些物品中选择一些装入背包要求背包中物品的总重量不超过C且总价值最大。
接下来以一个题目来进行讲解 题目描述
阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N ( N ≤ 100 ) N(N \le 100) N(N≤100) 堆金币第 i i i 堆金币的总重量和总价值分别是 m i , v i ( 1 ≤ m i , v i ≤ 100 ) m_i,v_i(1\le m_i,v_i \le 100) mi,vi(1≤mi,vi≤100)。阿里巴巴有一个承重量为 T ( T ≤ 1000 ) T(T \le 1000) T(T≤1000) 的背包但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割分割完的金币重量价值比也就是单位价格不变。请问阿里巴巴最多可以拿走多少价值的金币
输入格式
第一行两个整数 N , T N,T N,T。
接下来 N N N 行每行两个整数 m i , v i m_i,v_i mi,vi。
输出格式
一个实数表示答案输出两位小数
样例
样例输入
4 50
10 60
20 100
30 120
15 45样例输出 #1
240.00【题目来源】
洛谷 P2240 【深基12.例1】部分背包问题 题目解析
根据题目可知金币堆可以拆分并将价值最大的情况带走。对于此题我们需求出每堆金币的单价找出单价最高的然后依次搜索到背包装满。 Created with Raphaël 2.3.0 开始 找出单价最高的金币堆 装走金币 背包装满? 结束 yes no 根据此流程图可写出代码
#include iostream
#include iomanip
using namespace std;
int main() {int n, t;float money0;float a[100][3];cin n t;for (int i 0; i n; i)for (int j 0; j 2; j) {cin a[i][j];a[i][2] a[i][1] / a[i][0];}
to:float max 0;int max_num;for (int i 0; i n; i) {if (max a[i][2]) {max a[i][2];max_num i;}}if (t a[max_num][0]) {money t * max;}else {money a[max_num][0] * max;t t - a[max_num][0];a[max_num][2] 0;goto to;}cout fixed setprecision(2) money;return 0;
}2.3 简单数学证明问题
在数学问题中存在多分支的情况下不知道最优解时可用贪心算法找出最优解。 题目描述
有 n n n 个人在一个水龙头前排队接水假如每个人接水的时间为 T i T_i Ti请编程找出这 n n n 个人排队的一种顺序使得 n n n 个人的平均等待时间最小。
输入格式
第一行为一个整数 n n n。
第二行 n n n 个整数第 i i i 个整数 T i T_i Ti 表示第 i i i 个人的等待时间 T i T_i Ti。
输出格式
输出文件有两行第一行为一种平均时间最短的排队顺序第二行为这种排列方案下的平均等待时间输出结果精确到小数点后两位。
样例
样例输入
10
56 12 1 99 1000 234 33 55 99 812样例输出
3 2 7 8 1 4 9 6 10 5
291.90提示 1 ≤ n ≤ 1000 1\le n \leq 1000 1≤n≤1000 1 ≤ t i ≤ 1 0 6 1\le t_i \leq 10^6 1≤ti≤106不保证 t i t_i ti 不重复。
【题目来源】
洛谷 P1223 排队接水 题目解析 根据题目可知道要让平均等待时长最少就需要将总等待时长控制在最小因此需要将用时最短的人最先安排接水就可以得到最短总时长。数学表达式如下 m i n _ t i m e ∑ i 1 n ( n − i ) T i min\_time \sum_{i1}^{n} (n-i)T_i min_timei1∑n(n−i)Ti 此题通过简单的排序算法即可解决。代码如下
#include iostream
#include iomanip
using namespace std;
int main() {double t 0;int n;int a[1001][2];cin n;for (int i 1; i n; i) {cin a[i][0];a[i][1] i;}for (int i 1; i n ; i) {for (int j 1; j n - i; j) {if (a[j][0] a[j 1][0]) {int temp a[j 1][0];a[j1][0] a[j][0];a[j][0] temp;int temp1 a[j 1][1];a[j1][1] a[j][1];a[j][1] temp1;}}}for (int i 1; i n; i) {cout a[i][1] ;t (n - i) * a[i][0];}t t / n;cout fixed setprecision(2) endl t;
}三、总结
贪心算法所作的选择来源于以往的选择并非将来的选择。贪心算法相对于其他算法有一定的速度优势在一题可以多解的情况下可以优先选择贪心算法。
