• 贪心算法
  • 一、 算法概述
    • 1、 简介
    • 2、 基本步骤
  • 二、 基本实现
    • 1、 实例
    • 2、 分析步骤
    • 3、 代码实现
  • 三、 数模实战
    • 1、 题目展示
    • 2、 题目分析
    • 3、 代码实现
      • 3.1 初始化数据
      • 3.2 分发DVD
      • 3.3 分配余量
      • 3.4 数据存储
    • 4、 总代码

贪心算法

一、 算法概述

1、 简介

贪心算法，又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。[1]比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。在不同情况，选择最优的解，可能会导致辛普森悖论，不一定出现最优的解。

2、 基本步骤

1. 从某个初始解出发；
2. 采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；
3. 将所有解综合起来。

二、 基本实现

1、 实例

这里，我们先使用一个找零钱的例子来模拟这个算法

找零钱问题假设你开了间小店，不能电子支付，钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户 41 分钱的硬币，如何安排才能找给客人的钱既正确且硬币的个数又最少？这里需要明确的几个点：1.货币只有 25 分、10 分、5 分和 1 分四种硬币；2.找给客户 41 分钱的硬币；3.硬币最少化思考，能使用我们今天学到的贪婪算法吗？怎么做？

2、 分析步骤

1. 初始解，我们可以从想找给顾客小于41中最大的硬币
2. 使用迭代，不断的给客户找尽可能大的硬币，这样才能实现个数少的要求
3. 将所有解综合起来

3、 代码实现

这里我们采用python来实现这个算法

#!/usr/bin/python3
# -*- coding: UTF-8 -*-
__author__ = "A.L.Kun"
__file__ = "test.py"
__time__ = "2022/7/24 12:16"

coin = [25, 10, 1, 5]  # 所有类型的硬币
coin.sort()  # 先对硬币的面值进行排序，后面采用出栈的形式来获取数据
# 定一个字典，存储使用了多少硬币
dic = {25: 0, 10: 0, 5: 0, 1: 0}  # 初始化字典
# 确定初始解
value = 41 - coin[-1]  # 初始条件为减去一个最大的值
dic[coin[-1]] += 1  # 这个也要自加1
while value > 0 and coin:  # 如果我们把钱找完，并且可以把
    if value - coin[-1] >= 0:
        value -= coin[-1]  # 对面值进行相减
        dic[coin[-1]] += 1  # 计数中自加1
    else:
        coin.pop()  # 如果不能再相减的话，就把这个硬币给弹出，不在考虑

print(dic)  # 最后我们输出结果

三、 数模实战

1、 题目展示

这里，我们使用的题目是2005年的数学建模大赛B，第二问：

表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线订单（表2的数据格式示例如下表2，具体数据请从http://mcm.edu.cn/mcm05/problems2005c.asp下载），如何对这些DVD进行分配，才能使会员获得最大的满意度？请具体列出前30位会员（即C0001~C0030）分别获得哪些DVD。

数据请自己从网上下载哦！

表2：

2、 题目分析

1. 对于库存的100种光盘，首先满足所有对它偏爱顺序为1的会员的需要，即将每种光盘分配给所有对其偏爱顺序为1的会员，如果该光盘的数目偏少无法完成此次分配，则先分配给其中编号较小 的那些会员
2. 对于剩余光盘，再优先满足对它偏爱顺序为2的会员需要，同样地，如果该光盘的数 目偏少无法完成此次分配，则先分配给其中编号较小的那些会员
3. 依此类推分配下去，在以后分配时，已经拥有3张光盘的会员不参加分配
4. 如果还有剩下的光盘，随机分配给尚未分满的会员，分配结束

3、 代码实现

这里，我展示一下，我对这个贪心算法的理解，展示一下我的代码，有问题请多多指正：

3.1 初始化数据

这里，我们要先把Excel中的数据清洗出来，这样我们更好处理：

def init_data(
        io: str = "./B2005Table2.xls"  # 传入Excel表格的路径
) -> (defaultdict, dict):  # 初始化数据的函数
    """读取Excel中的数据，并且对数据进行清洗"""
    data_num = defaultdict(dict)  # 存存储成员的对所有数据的喜爱程度

    df = pd.read_excel(io)  # 读取Excel数据
    data = df[0:].iloc[:, 1:]  # 获取到关于所有的用户愿意观看的程度，以及所有的用户信息

    # 初始化DVD的全部信息
    col_index = data.columns[1:].tolist()  # 获取到每一种DVD
    capacity = data.loc[0, col_index].tolist()  # 获取到每一种DVD有多少张
    dic_goods = dict(zip(col_index, capacity))  # 转换为映射关系，更好访问
    # 初始化会员的全部信息
    for col_index_ in col_index:  # 得到每一列
        for row_index in data.index[1:]:  # 遍历每一列
            temp = dict()  # 设置临时变量
            name = data.loc[row_index, "Unnamed: 1"]  # 获取名字
            satisfaction = 40 - int(data.loc[row_index, col_index_]) if data.loc[
                row_index, col_index_] else 0.0  # 设置满意度
            if data_num.get(name):  # 判断是否存在name，如果存在
                temp = data_num[name]  # 把原来的数据拷贝出来
            temp[col_index_] = satisfaction  # 把新的满意度存入
            data_num.update({
                name: temp
            })  # 更新数据
    return data_num, dic_goods  # 返回获取到的满意度映射表，以及商品余量映射表

3.2 分发DVD

def get_max(
        dic: dict,  # 满意度映射表
):
    """获取最大值"""
    max_ = list(dic.keys())[0]  # 默认第一个键值对为最大值
    for key, value in dic.items():
        if value > dic[max_]:
            max_ = key

    return max_  # 返回最大值


def distribution(
        data_num: defaultdict,  # 满意度映射表
        dic_goods: dict  # 商品余量映射表
):
    """满足每一个会员的优先需求"""
    for name, dic in data_num.items():  # 遍历每一个字典
        temp_dic = dic.copy()  # 防止其修改原来字典的值
        max_ = get_max(temp_dic)  # 获取最大值
        value = temp_dic[max_]  # 进行对while循环的判断
        while temp_dic and value:  # 如果最终没货的话，就不用管了，同时，如果把每个人的感兴趣的东西选完，就没必要去选了，这个while循环就可以对成员对的多个满意度进行迭代，然后进行光盘的分配
            max_ = get_max(temp_dic)  # 获取最大值、
            value = temp_dic[max_]  # 进行对while循环的判断
            temp_dic.pop(max_)  # 获取里面最大的字典，并把这个键值对删除，但是不会删除主字典里面的值
            if len(selected_con[name]) < 3:  # 最基本的条件
                if dic_goods[max_] > 0:
                    # 如果DVD有货，并且用户没有获得3个DVD
                    selected_con[name].append(max_)  # 把光盘添加到主容器中
                    dic_goods[max_] -= 1  # 把商品数据去除
            else:  # 如果满了的话，就不用考虑了
                break

3.3 分配余量

剩余的没有分配到DVD的会员，我们需要重新对其进行随机分配，因为剩余的会员大部分都是没有获取到喜好的类型的DVD，对剩余DVD的兴趣为0，我们在这里可以随机对其进行分配，直到每个人都拥有DVD

def validation(
        dic_goods: dict  # 商品余量映射表
):
    """对没有分满的会员进行随机分配"""
    unselected = []  # 存储没有分满的会员
    for name, lis in selected_con.items():  # 获取出没有不满的人
        if len(lis) < 3:
            unselected.append({
                "name": name,  # 存储没有补满的会员名单
                "count": 3 - len(lis)  # 保存剩余的商品数量
            })
    # 对没有分满的人进行随机补全
    for dic in unselected:  # 对每个会员进行添加数据
        for index in range(dic["count"]):  # 补全剩余的商品数量
            while True:
                # 添加的数据进行随机化
                add_name = random.choice(list(dic_goods.keys()))  # 随机获取要添加的人
                if dic_goods[add_name] > 0:
                    selected_con[dic["name"]].append(add_name)  # 添加数据
                    dic_goods[add_name] -= 1  # 自减1
                    break

3.4 数据存储

运算完后，我们需要将数据写入Excel文件中，进行分析和存储：

def write_to_excel(
        satisfaction: dict,  # 满意度映射表
        io_selected: str = "./selected.xlsx",  # 存储路径
):
    """将得到DVD的成员写入Excel中"""

    book = Workbook()
    sheet = book.active
    sheet.title = "已分配到DVD的成员"
    sheet.cell(1, 1).value = '序号'
    sheet.cell(1, 2).value = '名字'
    sheet.cell(1, 3).value = 'DVD_1'
    sheet.cell(1, 4).value = 'DVD_2'
    sheet.cell(1, 5).value = 'DVD_3'
    row_index = 1
    index = 0
    for name, lis in selected_con.items():
        sheet.cell(row_index + 1, 1).value = index + 1
        sheet.cell(row_index + 1, 2).value = name
        lis_0 = f"{lis[0]} / {satisfaction[name][lis[0]]}"  # 类型 / 满意度
        sheet.cell(row_index + 1, 3).value = lis_0
        lis_1 = f"{lis[1]} / {satisfaction[name][lis[1]]}"
        sheet.cell(row_index + 1, 4).value = lis_1
        lis_2 = f"{lis[2]} / {satisfaction[name][lis[2]]}"
        sheet.cell(row_index + 1, 5).value = lis_2

        get_sum = satisfaction[name][lis[0]] + satisfaction[name][lis[1]] + satisfaction[name][lis[2]]

        row_index += 1
        index += 1
    book.save(io_selected)

4、 总代码

#!/usr/bin/python3
# -*- coding: UTF-8 -*-
__author__ = "A.L.Kun"
__file__ = "demo2.py"
__time__ = "2022/7/24 16:45"

import pandas as pd
from collections import defaultdict
from openpyxl import Workbook
import random

selected_con = defaultdict(list)  # 存储筛选出来的用户

def init_data(
        io: str = "./B2005Table2.xls"  # 传入Excel表格的路径
) -> (defaultdict, dict):  # 初始化数据的函数
    """读取Excel中的数据，并且对数据进行清洗"""
    data_num = defaultdict(dict)  # 存存储成员的对所有数据的喜爱程度

    df = pd.read_excel(io)  # 读取Excel数据
    data = df[0:].iloc[:, 1:]  # 获取到关于所有的用户愿意观看的程度，以及所有的用户信息

    # 初始化DVD的全部信息
    col_index = data.columns[1:].tolist()  # 获取到每一种DVD
    capacity = data.loc[0, col_index].tolist()  # 获取到每一种DVD有多少张
    dic_goods = dict(zip(col_index, capacity))  # 转换为映射关系，更好访问
    # 初始化会员的全部信息
    for col_index_ in col_index:  # 得到每一列
        for row_index in data.index[1:]:  # 遍历每一列
            temp = dict()  # 设置临时变量
            name = data.loc[row_index, "Unnamed: 1"]  # 获取名字
            satisfaction = 40 - int(data.loc[row_index, col_index_]) if data.loc[
                row_index, col_index_] else 0.0  # 设置满意度
            if data_num.get(name):  # 判断是否存在name，如果存在
                temp = data_num[name]  # 把原来的数据拷贝出来
            temp[col_index_] = satisfaction  # 把新的满意度存入
            data_num.update({
                name: temp
            })  # 更新数据
    return data_num, dic_goods  # 返回获取到的满意度映射表，以及商品余量映射表


def get_max(
        dic: dict,  # 满意度映射表
):
    """获取最大值"""
    max_ = list(dic.keys())[0]  # 默认第一个键值对为最大值
    for key, value in dic.items():
        if value > dic[max_]:
            max_ = key

    return max_  # 返回最大值


def distribution(
        data_num: defaultdict,  # 满意度映射表
        dic_goods: dict  # 商品余量映射表
):
    """满足每一个会员的优先需求"""
    for name, dic in data_num.items():  # 遍历每一个字典
        temp_dic = dic.copy()  # 防止其修改原来字典的值
        max_ = get_max(temp_dic)  # 获取最大值
        value = temp_dic[max_]  # 进行对while循环的判断
        while temp_dic and value:  # 如果最终没货的话，就不用管了，同时，如果把每个人的感兴趣的东西选完，就没必要去选了
            max_ = get_max(temp_dic)  # 获取最大值、
            value = temp_dic[max_]  # 进行对while循环的判断
            temp_dic.pop(max_)  # 获取里面最大的字典，并把这个键值对删除，但是不会删除主字典里面的值
            if len(selected_con[name]) < 3:  # 最基本的条件
                if dic_goods[max_] > 0:
                    # 如果DVD有货，并且用户没有获得3个DVD
                    selected_con[name].append(max_)  # 把光盘添加到主容器中
                    dic_goods[max_] -= 1  # 把商品数据去除
            else:  # 如果满了的话，就不用考虑了
                break


def write_to_excel(
        satisfaction: dict,  # 满意度映射表
        io_selected: str = "./selected.xlsx",  # 存储路径
):
    """将得到DVD的成员写入Excel中"""

    book = Workbook()
    sheet = book.active
    sheet.title = "已分配到DVD的成员"
    sheet.cell(1, 1).value = '序号'
    sheet.cell(1, 2).value = '名字'
    sheet.cell(1, 3).value = 'DVD_1'
    sheet.cell(1, 4).value = 'DVD_2'
    sheet.cell(1, 5).value = 'DVD_3'
    row_index = 1
    index = 0
    for name, lis in selected_con.items():
        sheet.cell(row_index + 1, 1).value = index + 1
        sheet.cell(row_index + 1, 2).value = name
        lis_0 = f"{lis[0]} / {satisfaction[name][lis[0]]}"  # 类型 / 满意度
        sheet.cell(row_index + 1, 3).value = lis_0
        lis_1 = f"{lis[1]} / {satisfaction[name][lis[1]]}"
        sheet.cell(row_index + 1, 4).value = lis_1
        lis_2 = f"{lis[2]} / {satisfaction[name][lis[2]]}"
        sheet.cell(row_index + 1, 5).value = lis_2

        get_sum = satisfaction[name][lis[0]] + satisfaction[name][lis[1]] + satisfaction[name][lis[2]]

        row_index += 1
        index += 1
    book.save(io_selected)


def validation(
        dic_goods: dict  # 商品余量映射表
):
    """对没有分满的会员进行随机分配"""
    unselected = []  # 存储没有分满的会员
    for name, lis in selected_con.items():  # 获取出没有不满的人
        if len(lis) < 3:
            unselected.append({
                "name": name,  # 存储没有补满的会员名单
                "count": 3 - len(lis)  # 保存剩余的商品数量
            })
    # 对没有分满的人进行随机补全
    for dic in unselected:  # 对每个会员进行添加数据
        for index in range(dic["count"]):  # 补全剩余的商品数量
            while True:
                # 添加的数据进行随机化
                add_name = random.choice(list(dic_goods.keys()))  # 随机获取要添加的人
                if dic_goods[add_name] > 0:
                    selected_con[dic["name"]].append(add_name)  # 添加数据
                    dic_goods[add_name] -= 1  # 自减1
                    break


def main():
    data_num, dic_goods = init_data()  # 初始化数据
    distribution(data_num, dic_goods)  # 初始化数据，同时获取结果
    validation(dic_goods)  # 那么剩余的都是一些没有分配到喜欢的DVD的对象了
    write_to_excel(data_num)  # 写入Excel表中


if __name__ == '__main__':
    main()