贪心算法：基础入门篇-Toy模板网

这篇具有很好参考价值的文章主要介绍了贪心算法：基础入门篇。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

贪心算法：基础入门篇

一、认识贪心算法

在求最优解的问题中，以某种贪心标准，从状态的最初始找到每一步最优解，通过多次的贪心求解，最终得到整个问题的最优解，此种解题的方法为贪心算法。可见贪心算法并不是一种固定的算法，而是根据问题的条件而产生的一种解决问题的思维模式。

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

二、常见贪心问题

2.1 纸牌问题

纸牌问题是最简单，也最好理解的贪心问题，题目如下：

题目描述:

有 $N$ 堆纸牌，编号分别为 $1,2,\ldots,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,\ldots,A_N$ ，表示每堆纸牌初始时的纸牌数。

输出格式:

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

样例：

样例输入

4
9 8 17 6

样例输出

提示

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

【题目来源】

NOIP 2002 提高组第一题

题目解析：

根据移牌规则，可以得出以下通式：
$\left\{\begin{matrix}a_i> ave,a_{i+1}=(a_i-ave)+a_{i+1}\\a_i=ave \\a_i< ave,a_{i+1}=a_{i+1}-(ave-a_i)\end{matrix}\right.$
在左至右开始排列的情况下，从移牌规则中可得知，大于平均数的牌只能向左移动，反之小于平均数的牌只能向右移动。由此可以画出以下关系图：

根据上述思路即可写出相应代码：

#include <iostream>
using namespace std;
int main(){
    int a,sum=0,ave=0;
    int b[100];
    cin>>a;
    for(int i=0;i<a;i++){
        cin>>b[i];
        ave+=b[i];
    }
    ave=ave/a;
    for(int i=0;i<a;i++){
        if(b[i]>ave){
            b[i+1]+=b[i]-ave;
            sum++;
        }
        if(ave>b[i]){
            b[i+1]=b[i+1]-(ave-b[i]);
            sum++;
        }
    }
    cout<<sum;
    return 0;
}

2.2 背包问题（基础版）

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

接下来以一个题目来进行讲解：
题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 $\le 100)$ 堆金币，第 $i$ 堆金币的总重量和总价值分别是 $m_i,v_i(1\le m_i,v_i \le 100)$ 。阿里巴巴有一个承重量为 $\le 1000)$ 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

输入格式

第一行两个整数 $N, T$ 。

接下来 $N$ 行，每行两个整数 $m_i,v_i$ 。

输出格式

一个实数表示答案，输出两位小数

样例

样例输入

样例输出 #1

240.00

【题目来源】

洛谷 P2240 【深基12.例1】部分背包问题

题目解析：

根据题目可知，金币堆可以拆分，并将价值最大的情况带走。对于此题，我们需求出每堆金币的单价，找出单价最高的，然后依次搜索，到背包装满。

根据此流程图可写出代码：

#include <iostream>
#include <iomanip>
using namespace std;
int main() {
    int n, t;
    float money=0;
    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$ 个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$ ，请编程找出这 $n$ 个人排队的一种顺序，使得 $n$ 个人的平均等待时间最小。

输入格式

第一行为一个整数 $n$ 。

第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的等待时间 $T_i$ 。

输出格式

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

样例

样例输入

10 
56 12 1 99 1000 234 33 55 99 812

样例输出

3 2 7 8 1 4 9 6 10 5
291.90

提示

$1\le n \leq 1000$ ， $1\le t_i \leq 10^6$ ，不保证 $t_i$ 不重复。

【题目来源】

洛谷 P1223 排队接水

题目解析：
根据题目可知道，要让平均等待时长最少，就需要将总等待时长控制在最小，因此需要将用时最短的人，最先安排接水，就可以得到最短总时长。数学表达式如下：
$f_{min\_time}(x)= \sum_{i=1}^{n} (n-i)T_i$
此题通过简单的排序算法，即可解决。代码如下：

#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[j+1][0] = a[j][0];
                a[j][0] = temp;
                int temp1 = a[j + 1][1];
                a[j+1][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;
}