哪种算法以统一的顺序排列一组具有不同数量的作业

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列表。