貪心演算法
- 一、演算法概述
  - 1、簡介
  - 2、基本步驟
- 二、基本實作
  - 1、實體
  - 2、分析步驟
  - 3、代碼實作
- 三、數模實戰
  - 1、題目展示
  - 2、題目分析
  - 3、代碼實作
    - 3.1 初始化資料
    - 3.2 分發DVD
    - 3.3 分配余量
    - 3.4 資料存盤
  - 4、總代碼

貪心演算法

一、演算法概述

1、簡介

貪心演算法，又稱貪婪演算法，是一種在每一步選擇中都采取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是最好或最優的演算法，[1]比如在旅行推銷員問題中，如果旅行員每次都選擇最近的城市，那這就是一種貪心演算法，

貪心演算法在有最優子結構的問題中尤為有效，最優子結構的意思是區域最優解能決定全域最優解，簡單地說，問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解，

貪心演算法與動態規劃的不同在于它對每個子問題的解決方案都做出選擇，不能回退，動態規劃則會保存以前的運算結果，并根據以前的結果對當前進行選擇，有回退功能，

貪心法可以解決一些最優化問題，如：求圖中的最小生成樹、求哈夫曼編碼……對于其他問題，貪心法一般不能得到我們所要求的答案，一旦一個問題可以通過貪心法來解決，那么貪心法一般是解決這個問題的最好辦法，由于貪心法的高效性以及其所求得的答案比較接近最優結果，貪心法也可以用作輔助演算法或者直接解決一些要求結果不特別精確的問題，在不同情況，選擇最優的解，可能會導致辛普森悖論，不一定出現最優的解，

2、基本步驟

從某個初始解出發；
采用迭代的程序，當可以向目標前進一步時，就根據區域最優策略，得到一部分解，縮小問題規模；
將所有解綜合起來，

二、基本實作

1、實體

這里，我們先使用一個找零錢的例子來模擬這個演算法

找零錢問題假設你開了間小店，不能電子支付，錢柜里的貨幣只有 25 分、10 分、5 分和 1 分四種硬幣，如果你是售貨員且要找給客戶 41 分錢的硬幣，如何安排才能找給客人的錢既正確且硬幣的個數又最少？這里需要明確的幾個點：1.貨幣只有 25 分、10 分、5 分和 1 分四種硬幣；2.找給客戶 41 分錢的硬幣；3.硬幣最少化思考，能使用我們今天學到的貪婪演算法嗎？怎么做？

2、分析步驟

初始解，我們可以從想找給顧客小于41中最大的硬幣
使用迭代，不斷的給客戶找盡可能大的硬幣，這樣才能實作個數少的要求
將所有解綜合起來

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 = https://www.cnblogs.com/liuzhongkun/p/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：

DVD編號	D001	D002	D003	D004	…
DVD現有數量	10	40	15	20	…
C0001	6	0	0	0	…
C0002	0	0	0	0	…
C0003	0	0	0	3	…
C0004	0	0	0	0	…
…	…	…	…	…	…

2、題目分析

對于庫存的100種光碟，首先滿足所有對它偏愛順序為1的會員的需要，即將每種光碟分配給所有對其偏愛順序為1的會員，如果該光碟的數目偏少無法完成此次分配，則先分配給其中編號較小的那些會員
對于剩余光碟，再優先滿足對它偏愛順序為2的會員需要，同樣地，如果該光碟的數目偏少無法完成此次分配，則先分配給其中編號較小的那些會員
依此類推分配下去，在以后分配時，已經擁有3張光碟的會員不參加分配
如果還有剩下的光碟，隨機分配給尚未分滿的會員，分配結束

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 = https://www.cnblogs.com/liuzhongkun/p/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 = https://www.cnblogs.com/liuzhongkun/p/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 = 'https://www.cnblogs.com/liuzhongkun/p/序號'
    sheet.cell(1, 2).value = 'https://www.cnblogs.com/liuzhongkun/p/名字'
    sheet.cell(1, 3).value = 'https://www.cnblogs.com/liuzhongkun/p/DVD_1'
    sheet.cell(1, 4).value = 'https://www.cnblogs.com/liuzhongkun/p/DVD_2'
    sheet.cell(1, 5).value = 'https://www.cnblogs.com/liuzhongkun/p/DVD_3'
    row_index = 1
    index = 0
    for name, lis in selected_con.items():
        sheet.cell(row_index + 1, 1).value = https://www.cnblogs.com/liuzhongkun/p/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 = https://www.cnblogs.com/liuzhongkun/p/lis_0
        lis_1 = f"{lis[1]} / {satisfaction[name][lis[1]]}"
        sheet.cell(row_index + 1, 4).value = https://www.cnblogs.com/liuzhongkun/p/lis_1
        lis_2 = f"{lis[2]} / {satisfaction[name][lis[2]]}"
        sheet.cell(row_index + 1, 5).value = https://www.cnblogs.com/liuzhongkun/p/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 = https://www.cnblogs.com/liuzhongkun/p/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 = https://www.cnblogs.com/liuzhongkun/p/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 = 'https://www.cnblogs.com/liuzhongkun/p/序號'
    sheet.cell(1, 2).value = 'https://www.cnblogs.com/liuzhongkun/p/名字'
    sheet.cell(1, 3).value = 'https://www.cnblogs.com/liuzhongkun/p/DVD_1'
    sheet.cell(1, 4).value = 'https://www.cnblogs.com/liuzhongkun/p/DVD_2'
    sheet.cell(1, 5).value = 'https://www.cnblogs.com/liuzhongkun/p/DVD_3'
    row_index = 1
    index = 0
    for name, lis in selected_con.items():
        sheet.cell(row_index + 1, 1).value = https://www.cnblogs.com/liuzhongkun/p/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 = https://www.cnblogs.com/liuzhongkun/p/lis_0
        lis_1 = f"{lis[1]} / {satisfaction[name][lis[1]]}"
        sheet.cell(row_index + 1, 4).value = https://www.cnblogs.com/liuzhongkun/p/lis_1
        lis_2 = f"{lis[2]} / {satisfaction[name][lis[2]]}"
        sheet.cell(row_index + 1, 5).value = https://www.cnblogs.com/liuzhongkun/p/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()

本文來自博客園，作者：A-L-Kun，轉載請注明原文鏈接：https://www.cnblogs.com/liuzhongkun/p/16515759.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/500169.html

標籤：Python

上一篇：Python詞頻分析

下一篇：學生選課系統的專案開發

Python 實作貪心演算法

貪心演算法

一、 演算法概述

1、 簡介

2、 基本步驟

二、 基本實作

1、 實體

2、 分析步驟

3、 代碼實作

三、 數模實戰

1、 題目展示

2、 題目分析

3、 代碼實作

3.1 初始化資料

3.2 分發DVD

3.3 分配余量

3.4 資料存盤

4、 總代碼

一、演算法概述

1、簡介

2、基本步驟

二、基本實作

1、實體

2、分析步驟

3、代碼實作

三、數模實戰

1、題目展示

2、題目分析

3、代碼實作

4、總代碼