Python 实现贪心算法 - ToB企服应用市场:ToB评测及商务社交产业平台

#!/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) # 最后我们输出结果

复制代码

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: # 如果最终没货的话，就不用管了，同时，如果把每个人的感兴趣的东西选完，就没必要去选了，这个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

复制代码

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 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)

复制代码

#!/usr/bin/python3# -*- coding: UTF-8 -*-__author__ = "A.L.Kun"__file__ = "demo2.py"__time__ = "2022/7/24 16:45"import pandas as pdfrom collections import defaultdictfrom openpyxl import Workbookimport randomselected_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: # 如果满了的话，就不用考虑了 breakdef 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
breakdef 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()

复制代码