Какой алгоритм упорядочивает набор заданий с разными величинами в едином порядке?

Question

Пример

Учитывая количество различных типов задач , которые необходимо выполнить в течение периода в один месяц :

Type  |  Number per month
--------------------------
A     |  1
B     |  5
C     |  30
D     |  15
E     |  20
--------------------------
         71

Вопрос:

Как мне сгенерировать плоский порядок (одномерный массив) типов, который обеспечивает

• 71 задания выполняются в течение одного месяца
• типы распределяются максимально равномерно (ABAB вместо AABB)

Редактировать:

Одна идея, которая возникла в комментариях:

Возможно, уменьшение каждого стека типов на величину относительно его размера лучше, чемиспользовать абсолютное количество 1. например.A: 2, B: 10 приводит к тому, что «для каждого A берут 5 B», потому что B в пять раз больше, чем A.

Answer 1

Предположим, у вас есть массив типов задач, таких как:

types = [[:A,1],[:B,5],[:C,6],[:D,2],[:E,3]]

Вы можете сначала отсортировать, а затем использовать большее число в качестве контрольной точки для построения массива задач.

Пример:

types = [[:A,1],[:B,5],[:C,6],[:D,2],[:E,3]]
tasks=[]; i=0

asc = types.sort {|a,b| a[1] <=> b[1] }
max = asc[types.length-1][1]

(1..max).to_a.each do |i|
    types.each {|t| tasks << t[0] if t[1] >= i}
end

puts tasks.inspect

производит:

[:A, :B, :C, :D, :E, :B, :C, :D, :E, :B, :C, :E, :B, :C, :B, :C, :C]

Answer 2

Обозначение: у вас есть набор X = {x1, ... xk}, где xi должен появиться в выходных ci раз.

Что-то вроде этого должно сделать это: Пусть C будет c1 + c2 .. + ck (71 в вашем примере). Вычислите шаг каждого элемента: si = C / ci. Вычислите предварительные местоположения для каждого элемента и составьте список (местоположения, элемент): locs_i = (si, i), (2 * si, i), ... (c_i * si, i) Объединить списки locs_i лексикографически.