贪心算法学习笔记

前言

没错没错，这篇咕咕咕了十几天的文章，终于迎来了她的更新！！！

这个蒟蒻的学习路线特别奇怪呢，一会学那个一会学这个。

几天混了这么多分区的蒟蒻居然没有忘本

基础

首先，我们需要知道，什么叫贪心。

贪心算法，也叫贪婪算法。贪心，顾名思义就是贪心地进行决策。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。

形象一点，就像是有一个贪婪的人，她每次选择的时候只顾眼前的优势，而不考虑将来的后果。 dy毒鸡汤：6

一个例子，假如现有 $1$ 分、$5$ 分、$25$ 分的硬币可用来找钱，现在我们需要找 $N=32$ 分的零钱，如何找？自然，我们先从面值大的来找：

首先找 $25$ 分钱，还剩 $7# 分钱。

自然，接下来我们找 $5$ 分钱，还剩 $2$ 分钱。

这 $2$ 分钱自然就只能用 $1$ 分的来找了。

于是到了最后，我们这32分就变成了1个25分、1个5分，以及2个1分了。

贪心的正确性

这是不得不提的一点：贪心，到底是不是正确的选择？

实际上，贪心决策的正确性是不能确定的，在这一个选硬币的例子中，确实是正确的。

但是这并不证明贪心就完全是对的，比如著名的01背包，这就需要用到DP了 本蒟蒻不会 qwq

背包的普遍题面是这样的：

有一个容量为 $V$ 的背包，还有 $n$ 个物体。现在忽略物体实际几何形状，我们认为只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即体积 $w$ 和价值 $v$ 。

问：如何向背包装物体才能使背包中物体的总价值最大？

看起来，我们可以直接使用贪心决策。

不过只要我们稍加验证，就发现我们不可以这么想，这是推倒贪心yyds的一个例子：

$V=10, n=4$

$w_1 = 8, v_1 = 9$
$w_2 = 3, v_2 = 3$
$w_3 = 4, v_3 = 4$
$w_4 = 3, v_4 = 3$

如果我们使用贪心的话，我们就应该选择性价比最高的物品：即$\frac{v}{w}$的值最大的的物品来放进背包。

显然，我们就可以优先拿第一个物品，因为$\frac{v_1}{w_1}=1.125$，而其余物品均为 $\frac{v}{w}=1$。

于是你拿了第一个东西，然后你会发现一个问题：这个背包装不下了！但是，其实它还有 $1$ 的空间。

So，贪心不能用的原因就是：它会出现浪费空间的现象，无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。

例题

贪心，有着许多经典的例题：

洛谷P1031 [NOIP2002 提高组] 均分纸牌

题面

点击查看题面

题目描述

有$N$堆纸牌，编号分别为 $1,2,…,N$。每堆上有若干张，但纸牌总数必为 $N$ 的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为 $1$ 堆上取的纸牌，只能移到编号为 $2$ 的堆上；在编号为 $N$ 的堆上取的纸牌，只能移到编号为 $N-1$ 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

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

例如 $N=4$ 时，$4$ 堆纸牌数分别为 $9,8,17,6$。

移动 $3$ 次可达到目的：

• 从第三堆取 $4$ 张牌放到第四堆，此时每堆纸牌数分别为 $9,8,13,10$。
• 从第三堆取 $3$ 张牌放到第二堆，此时每堆纸牌数分别为 $9,11,10,10$。
• 从第二堆取 $1$ 张牌放到第一堆，此时每堆纸牌数分别为 $10,10,10,10$。

输入格式

第一行共一个整数 $N$，表示纸牌堆数。
第二行共 $N$ 个整数 $A_1,A_2,\cdots,A_N$，表示每堆纸牌初始时的纸牌数。

输出格式

共一行，即所有堆均达到相等时的最少移动次数。

样例 #1

样例输入 #1

4
9 8 17 6

样例输出 #1

3

提示

对于 $100\%$ 的数据，$1 \le N \le 100$，$1 \le A_i \le 10000$。

【题目来源】

NOIP 2002 提高组第一题

解析

这道题采用取平均数的方法，然后咕咕咕？！