- 前言
- 总结
前言
一个比较复杂的多技能工人多任务分配问题，采用贪婪算法进行分配，以最低成本为目标，逻辑有点复杂，但是考虑到了各种情况，其中w1为工人1，列表表示工人具备s1,s3,s4技能，采用s1技能需要支付佣金为1，采用s3支付佣金为1.2，采用s4采用佣金为1.1，最多可同一任务使用两个技能，任务距离为7，以次类推。
T = [‘s1’,‘s2’,‘s3’,‘s4’,‘s5’]
T_num = [2, 3, 3, 2, 2]
这两个分别表示目标任务需要的技能T及其对应的数量T_num。本文实现的是单任务目标的贪婪算法实现，需要的话细致推理即可。
T = ['s1','s2','s3','s4','s5']
T_num = [2, 3, 3, 2, 2]
budget = 15
w1 = [[("s1",1), ("s3", 1.2), ("s4", 1.1)], 2, 7]
w2 = [[("s2",1.3), ("s4",1.2), ("s5",1.1)], 2, 11]
w3 = [[("s2",1.3), ("s3",1.3), ("s4",1.2), ("s5",1)], 3, 7]
w4 = [[("s1",1.1), ("s2",1.3), ("s3", 1.1)], 2,11]
w5 = [[("s3",1.3), ("s5",1.4)], 2, 7]
w6 = [[("s1",1), ("s2",1.2), ("s4",1.3)], 1, 8]
w7 = [[("s4",1.3), ("s5",1.3)], 2, 8]
w8 = [[("s3",1.3), ("s4",1.2)], 2, 8]
w9 = [[("s3",1.3), ("s4",1.2), ("s5",1)], 3,7.5]
w10 = [[("s1",1.1), ("s2",1.2), ("s4",1.3), ("s5",1.1)], 3, 7.5]
W = [w1, w2, w3, w4, w5, w6, w7, w8, w9, w10]
#计算工人对应技能成本
cost_w = []
s_w = []
for i in range(len(W)):
cost_w.append([])
s_w.append([])
for j in range(len(W[i][0])):
cost_w[i].append(W[i][0][j][1] + W[i][-1]*0.01)
s_w[i].append(W[i][0][j][0])
print(cost_w)
print(s_w)
tech_num = []
for i in W:
tech_num.append(i[-2])
print(tech_num)
#各技能最小值与对应技能
min_w_list = []
w_s_list = []
#工人采用技能初始化
workers = []
for i in range(len(cost_w)):
#工人成本最低技能
min_w = min(cost_w[i])
#对应技能索引
w_s = s_w[i][cost_w[i].index(min_w)]
min_w_list.append(min_w)
w_s_list.append(w_s)
workers.append(0)
print(min_w_list)
print(w_s_list)
print(workers)
T_taget = 0
for i in T_num:
T_taget += i
#最优选择
Topt = []
#计算可选用数量
zxxx = 0
for i in tech_num:
zxxx += i
while zxxx>0 and T_taget>0:
print("循环条件：",zxxx,T_taget)
#选择最小成本技能
min_choose = min(min_w_list)
#最小成本技能索引(对应工人)
index_c = min_w_list.index(min_choose)
#工人对应技能
cost_c = w_s_list[min_w_list.index(min_choose)]
#选择条件
print("选择条件：",T_num[T.index(cost_c)], tech_num[index_c])
#有目标技能需求
if T_num[T.index(cost_c)] > 0 :
#对应工人可以进行工作
if tech_num[index_c] > 0:
workers[index_c] += 1
W[index_c][-2] -= 1
Topt.append((index_c, cost_c))
#更改数量
T_num[T.index(cost_c)] -= 1
tech_num[index_c] -= 1
#删除该数据
ddd = s_w[index_c].index(cost_c)
s_w[index_c].pop(ddd)
dxx = cost_w[index_c].pop(ddd)
print(T_num)
T_taget = 0
for i in T_num:
T_taget += i
if T_taget == 0:
print("成功分配任务")
print("任务分配为：",Topt)
break
zxxx = 0
for i in tech_num:
zxxx += i
else:
cost_w.pop(index_c)
s_w.pop(index_c)
#没有对应技能需求
else:
for i in range(len(cost_w)):
if cost_c in s_w[i]:
ddd = s_w[i].index(cost_c)
s_w[i].pop(ddd)
cost_w[i].pop(ddd)
# 各技能最小值与对应技能
c_num = 0
for i in range(len(cost_w)):
c_num += len(cost_w[i])
print(c_num)
if c_num == 0:
print("无工人可用了")
print(Topt)
break
else:
min_w_list = []
w_s_list = []
print(cost_w)
for i in range(len(cost_w)):
# 工人成本最低技能
if cost_w[i] == []:
min_w = 10000
w_s = 's'
else:
min_w = min(cost_w[i])
w_s = s_w[i][cost_w[i].index(min_w)]
# 对应技能索引
min_w_list.append(min_w)
w_s_list.append(w_s)
print(min_w_list)
print(w_s_list)
总结
没啥总结的，如果要点个关注也行哈哈哈
