项目要求

从项目给出的信息中可以略窥一二，按数据划分的行也可以了解到：

---

工厂的数目n，消费者的数目m

---

工厂1的最大容量和开厂开销
工厂2的最大容量和开厂开销
…
…
…
工厂n的最大容量和开厂开销

---

m个消费者的各自需求

---

所有消费者分别到工厂1的开销
所有消费者分别到工厂2的开销
…
…
…
所有消费者分别到工厂n的开销

---

总开销=消费者开销+开厂开销
额外要求：单个工厂中各个消费者的需求之和不能超过其最大容量

需要关注的坑：

1.消费者和工厂相关的矩阵中行是工厂，列才是消费者，不能弄混了，贪心算法也是基于这个前提去实现才有价值
2.原数据的格式实在是一言难尽，，，不但数据不规整，一些数字后会多出个小数点，而且在行数和结尾的结束符上也有区别，花了不少时间加条件判断甄别。还好总体不算大问题

具体思路

1.贪心算法

第一个想法就是用局部最优的方法来解，也就是贪心算法。思路也比较清晰：对于每个消费者而言，先选取当前开销最小的工厂，若该消费者的需求小于该工厂的剩余容量，则匹配之；反之，寻找开销第二小的工厂，重复上述过程。我选择按顺序从前往后遍历所有消费者，得到一个相对最优的结果。由上述推论可知结果波动很大，一般都与数据的排布有关，局部最优，但整体来看并不是一种很好的解法
相关代码如下：

import time

allfile = ""
for line in open("p1","r"):                      #相关的数据文件已经放在python文件的目录下
    allfile = allfile + line
str = allfile.split()                            #已经切割好的字符串元组

data = []
for i in range(0, len(str)):
    if len(str[i]) > 10:
        break
    if str[i][-1] == '.':                        #源数据中一些莫名其妙的格式
        data.append(int(str[i][:-1]))
    else:
        data.append(int(str[i]))                 #将所有数据从string转为int类型存在data中

#设置所需的参数
facility_num = data[0]                           #工厂的数目
customer_num = data[1]                           #消费者数目
capacity = []                                    #工厂的容量
opening_cost = []                                #开厂开销
customer_demand = []                             #消费者需求
cost = []                                        #消费者开销

for i in range (0, facility_num):
    capacity.append(data[2 + i * 2])
    opening_cost.append(data[3 + i * 2])

for i in range(facility_num * 2 + 2, facility_num * 2 + customer_num + 2):
    customer_demand.append(data[i])

for i in range(facility_num * 2 + customer_num + 2, len(data)):
    cost.append(data[i])

all_cost = 0                                     #总开销
facility_table = []                              #维持一个工厂的开关表
for i in range(0, facility_num):
    facility_table.append(0)

#开始贪心算法,对消费者进行遍历

starttime = time.time()              #计时开始

for i in range(0, customer_num):
    one_customer_cost = []                       #单个消费者对应的元组
    for j in range(0, facility_num):
        if customer_demand[i] > capacity[j]:     #如果需求大于剩余容量，设置一个极大值导入元组
            one_customer_cost.append(100000)
        else:
            one_customer_cost.append(cost[i + customer_num * j])    #元组输入完毕
    min_index = one_customer_cost.index(min(one_customer_cost))     #在剩余合理的工厂目标中挑选一个最小的代价，返回索引
    facility_table[min_index] = 1                                   #工厂开关打开
    capacity[min_index] = capacity[min_index] - customer_demand[i]  #最大容量减小(减去的是该消费者的需求)
    all_cost = all_cost + cost[i + customer_num * min_index]        #总代价增加

#针对开关表加上开厂开销
for i in range (0, facility_num):
    if facility_table[i] == 1:
        all_cost = all_cost + opening_cost[i]

#计时结束
endtime = time.time()

print(all_cost)

print (endtime - starttime)

结果

	Result	Time(s)
p1	–	–
p2	–	–
p3	–	–
p4	–	–
p5	–	–
p6	–	–
p7	–	–
p8	–	–
p9	–	–
p10	–	–
p11	–	–
p12	–	–
p13	–	–
p14	–	–
p15	–	–
p16	–	–
p17	–	–
p18	–	–
p19	–	–
p20	–	–
p21	–	–
p22	–	–
p23	–	–
p24	–	–
p25	–	–
p26	–	–
p27	–	–
p28	–	–
p29	–	–
p30	–	–
p31	–	–
p32	–	–
p33	–	–
p34	–	–
p35	–	–
p36	–	–
p37	–	–
p38	–	–
p39	–	–
p40	–	–
p41	–	–
p42	–	–
p43	–	–
p44	–	–
p45	–	–
p46	–	–
p47	–	–
p48	–	–
p49	–	–
p50	–	–
p51	–	–
p52	–	–
p53
p54
p55
p56
p57
p58
p59
p60
p61
p62
p63
p64
p65
p66
p67
p68
p69
p70
p71