The real problem comes from LQA The personnel of the system distribute the workload , There are two ways , One is Average distribution , One is to distribute according to a given proportion . Unwanted AC, If you can get a solution that meets the meaning of the problem, you will achieve your goal .
One order The order contains a xls form , Contains several entries , It is necessary to assign entries to a number of LQA, It would be nice if the total number of words in each person's entries were approximately the same , It doesn't have to be exactly the same .
An entry cannot be separated , The proportion of allocated workload is based on the number of words .
Another application case is extended ：
It is known that there are now x A group ,（ There is a large gap between the groups , Fictitious 100 people , yes , we have 10 personal ,）, Need to share n Departments . requirement , The group cannot be split , The number of people in each department is relatively balanced . seek , Teams in each department .
Include one with m An array of integers is divided into n An array , The sum of each array should be as close as possible to
input：
# Given the group and its corresponding number
groups = {'a':100, 'b':10, 'c':23, 'd':23, 'e':12, 'f':34, 'g':67, 'h':135, 'i':5, 'j':39, 'k':60, 'l':204}
# Number of target departments
n = 5
output：
groups: [[204], [135], [100, 23], [67, 39, 12, 5], [60, 34, 23, 10]]
Here we refer to the student's ideas
https://cloud.tencent.com/developer/article/1659134
thank
According to the above ideas , The core idea is to traverse every time Array , Each trip produces a grouping list , Because it needs to be divided into 5 Group , So go ahead 5 Trip grouping , Each trip starts from the back .
The purpose of traversal is Compare each number in turn value, And the rest The average of the numbers avg（sum_leftover/(n-i), i Is the number of trips ）,
If value >=avg, Join in groups, Become a list, And end the loop directly （ Because it has been better than avg Big words , Adding any number will only deviate from avg, Increase variance ）
If value < avg, Join in groups, Become this trip list The first member of , Continue to cycle back , See if you can add a number , Bring this group closer to avg. Terminate this traversal after the loop ends .
Last trip , Then put all the remaining numbers in the last one groups The same list.
Original examples ：
The array is ：500, 18, 28, 2, 27, 35, 22, 10, 6, 5, 3, 2, 1; It is divided into 4 Group
The order is ：500, 35, 28, 27, 22, 18, 10, 6, 5, 3, 2, 2, 1
Calculate average avg = 164.75
Traversal array ：
The first round ：500 > avg, Take out 500 As a group ; The remaining array is 35, 28, 27, 22, 18, 10, 6, 5, 3, 2, 2, 1
Calculation avg = 53
The second round ：35 < avg, Take out 35 Put it in the second group ;
delta=53-35=18;
Next is 28 > 18, Continue traversing ,27 > 18,22 > 18,18 == 18, So take it out 18 Join the second group , End the second round , The remaining array is 28, 27, 22, 10, 6, 5, 3, 2, 2, 1
The third round ：28 < avg, Take out 28 Put it in the third group ;
delta=53-28=25
27 > delta > 22,27-delta=2,delta-22=3,distance = 2, take 22 Add temporary array ,delta = 3;
18 >3, ... ,5 > 3, 3==3,distance = delta-3 = 0; So will 22 and 3 Join the third group , End the third round , The array is 27, 10, 6, 5, 2, 2, 1
The fourth round ： Directly return the remaining number and add it to a group as the fourth group
result ：
arr 0 is : 500, sum = 500
arr 1 is : 35 18, sum = 53
arr 2 is : 28 22 3, sum = 53
arr 3 is : 27 10 6 5 2 2 1, sum = 53
After a general understanding, I started to do it directly , Without reference to the original go Code , The details were not specially considered , Like classics How to do dynamic planning for , For example, can we ignore the fact that the loop cannot remove Members' questions （ Dynamic change of length The iteration object of cannot be accessed again ）.
（ In the first implementation below Not in loop remove, Strictly abide by his grammar , But in fact , Because of this for In circulation , Will only be satisfied if Only when conditions permit remove operation （ Change in length ）, also remove immediately break Out of the loop , There will be no next cycle , So there's no mistake , Conform to grammatical norms , You can be bold remove, Many unnecessary variables can be reduced , I'm in To distribute in proportion I did ）
import numpy as np
def split(groups, n):
# Find the total
# Divide equally
values = [i for i in groups.values()]
values.sort(reverse=True)
print (values, "length:", len(values))
groups =[]
# values_copy = values.copy()
count_remove = 0
cnt_out = 0
for index in range(n):# Number of cycle groups
print (index)
if index == (n-1):
# The last time , Just list the rest as a group
groups_list = np.sum(groups)
# Two, please list The difference between the set
for num in groups_list:
if num in values:
values.remove(num)
groups.append(values)
print ("groups:",groups)
return groups
else:
cnt = 0
for value in values[cnt_out:]:
# Calculate the mean of the remaining numbers
avg = (sum(values) -np.sum(np.sum(groups)) )/(n - index)
print ("avg:", avg)
if value >= avg:
print ("value:", value)
count_remove += value
group = [value]
groups.append(group)
break# End this layer cycle , Continue to the next level of circulation
else:
group = [value]
count_remove += value
delta = avg-value
print ("delta:", delta)
# Find... In the following sequence x =dealta
print (cnt)
for i in values[cnt:]:
print ("searching in :", i)
if i <= delta:
group.append(i)
count_remove += i
delta -= i
groups.append(group)
break
cnt +=1
cnt_out +=1
The results are as follows , Roughly balanced （ The first is 204 Because of this 204 Can not be further divided ）
With the previous experience, this is much easier , Can be said to be split Method deformation , After deleting many meaningless variables , The code is as follows
Premise ： Before we start , First, the total number of people is calculated in proportion , Get the following standard group ：
input：
groups = {'a':100, 'b':10, 'c':23, 'd':23, 'e':12, 'f':34, 'g':67, 'h':135, 'i':5, 'j':39, 'k':60, 'l':204}
percents = [45, 20,20, 15]
n = 4
# After calculation
split_words = [320 , 142, 142, 106]
output：
You can calculate the expected results by yourself
import numpy as np
def split(groups, n, split_words):
values = [i for i in groups.values()]
values.sort(reverse=True)
print (values, "length:", len(values))
groups = []
for index in range(n):
standard = split_words[index]
if index == (n-1):
groups.append(values)
return groups
else:
for value in values:
if value > standard:
group = [value]
values.remove(value)
groups.append(group)
break
else:
group = [value]
values.remove(value)
delta =standard-value
for i in values:
print ("searching in :", i)
if i <= delta:
values.remove(i)
group.append(i)
delta -= i
groups.append(group)
break
result ：
Approximate to expected results , Achieve the goal ！
TODO： For business reasons , I haven't thought about numerical repetition for the time being .
This one looks more comfortable than the previous one , You can also modify the previous code according to this idea , Equally distributed codes can also use the method of first calculating the average value , Save later calculation cost , Welcome to discuss .
