纸牌问题2.2

在求最优解的问题中以某种贪心标准从状态的最初始找到每一步最优解通过多次的贪心求解最终得到整个问题的最优解此种解题的方法为贪心算法。

可见贪心算法并不是一种固定的算法而是根据问题的条件而产生的一种解决问题的思维模式。

由定义可知贪心算法是由局部的最优解得到总体的最优解因此在使用贪心算法之前要先判断问题是否适合使用贪心算法。

二、常见贪心问题

现在要求找出一种移动方法用最少的移动次数使每堆上纸牌数都一样多。

堆纸牌数分别为

ave,a_{i1}(a_i-ave)a_{i1}\\a_iave

\\a_i

ave,a_{i1}a_{i1}-(ave-a_i)\end{matrix}\right.

⎧​ai​ave,ai1​(ai​−ave)ai1​ai​aveai​ave,ai1​ai1​−(ave−ai​)​

在左至右开始排列的情况下从移牌规则中可得知大于平均数的牌只能向左移动反之小于平均数的牌只能向右移动。

由此可以画出以下关系图

ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GasOavLMVwCUmave

.error-icon{fill:#552222;}#mermaid-svg-GasOavLMVwCUmave

.error-text{fill:#552222;stroke:#552222;}#mermaid-svg-GasOavLMVwCUmave

.edge-thickness-normal{stroke-width:2px;}#mermaid-svg-GasOavLMVwCUmave

.edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-GasOavLMVwCUmave

.edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-GasOavLMVwCUmave

.edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-GasOavLMVwCUmave

.edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-GasOavLMVwCUmave

.marker{fill:#333333;stroke:#333333;}#mermaid-svg-GasOavLMVwCUmave

.marker.cross{stroke:#333333;}#mermaid-svg-GasOavLMVwCUmave

ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-GasOavLMVwCUmave

ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-GasOavLMVwCUmave

.cluster-label

text{fill:#333;}#mermaid-svg-GasOavLMVwCUmave

.cluster-label

span{color:#333;}#mermaid-svg-GasOavLMVwCUmave

.label

text,#mermaid-svg-GasOavLMVwCUmave

span{fill:#333;color:#333;}#mermaid-svg-GasOavLMVwCUmave

.node

rect,#mermaid-svg-GasOavLMVwCUmave

.node

circle,#mermaid-svg-GasOavLMVwCUmave

.node

ellipse,#mermaid-svg-GasOavLMVwCUmave

.node

polygon,#mermaid-svg-GasOavLMVwCUmave

.node

path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-GasOavLMVwCUmave

.node

.label{text-align:center;}#mermaid-svg-GasOavLMVwCUmave

.node.clickable{cursor:pointer;}#mermaid-svg-GasOavLMVwCUmave

.arrowheadPath{fill:#333333;}#mermaid-svg-GasOavLMVwCUmave

.edgePath

.path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-GasOavLMVwCUmave

.flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-GasOavLMVwCUmave

.edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-GasOavLMVwCUmave

.edgeLabel

rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-GasOavLMVwCUmave

.cluster

rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-GasOavLMVwCUmave

.cluster

text{fill:#333;}#mermaid-svg-GasOavLMVwCUmave

.cluster

span{color:#333;}#mermaid-svg-GasOavLMVwCUmave

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%,

#aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-GasOavLMVwCUmave

:root{--mermaid-font-family:"trebuchet

第一堆

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

}2.2

背包问题是贪心算法中比较经典的贪心问题同时背包问题也是一个经典的动态规划问题其基本形式是给定一个背包容量为C和一组物品每个物品有自己的重量和价值现在从这些物品中选择一些装入背包要求背包中物品的总重量不超过C且总价值最大。

题目描述

mi​,vi​(1≤mi​,vi​≤100)。

阿里巴巴有一个承重量为

1000

的背包但并不一定有办法将全部的金币都装进去。

他想装走尽可能多价值的金币。

所有金币都可以随意分割分割完的金币重量价值比也就是单位价格不变。

请问阿里巴巴最多可以拿走多少价值的金币

输入格式

根据题目可知金币堆可以拆分并将价值最大的情况带走。

对于此题我们需求出每堆金币的单价找出单价最高的然后依次搜索到背包装满。

Created

在数学问题中存在多分支的情况下不知道最优解时可用贪心算法找出最优解。

题目描述

输出文件有两行第一行为一种平均时间最短的排队顺序第二行为这种排列方案下的平均等待时间输出结果精确到小数点后两位。

样例输入

根据题目可知道要让平均等待时长最少就需要将总等待时长控制在最小因此需要将用时最短的人最先安排接水就可以得到最短总时长。

数学表达式如下

f_{min\_time}(x)

贪心算法所作的选择来源于以往的选择并非将来的选择。

贪心算法相对于其他算法有一定的速度优势在一题可以多解的情况下可以优先选择贪心算法。