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

发布于 2024-11-30 21:49:39 字数 633 浏览 0 评论 0原文

示例

给定许多不同的任务类型，需要在一个月的时间内完成：

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 大五倍。

原文

Example

Given a number of different task types that need to be completed over a period of one month:

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

Question:

How do I generate a flat order (1-dimensional array) of types that ensures that

71 jobs are completed within one month
the types are spreaded as equally as possible (ABAB instead of AABB)

Edit:

One Idea that came up in the comments is:

Maybe reducing each stack of types by an amount relative to its size
is better than to use the absolute amount of 1. eg. A:2, B:10 results
in "for each A take 5 B" because B is five times larger than A.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

孤独难免 2024-12-07 21:49:39

假设您有一个任务类型数组，例如：

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]

Assume you have an array of task types such as:

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

You can first sort, and then use the greater number as reference point to build the array of tasks.

Example:

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

produces:

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

回复收藏 0 原文

意中人 2024-12-07 21:49:39

表示法：您有一个集合 X={x1,...xk}，其中 xi 需要出现在输出 ci 次中。

像这样的事情应该这样做：
令 C 为 c1+c2..+ck （在您的示例中为 71）。
计算每个项目的步幅：si = C/ci。
计算每个项目的暂定位置并创建一个 (location,item) 列表：
locs_i = (si,i), (2*si,i), ... (c_i*si,i)
按字典顺序合并 locs_i 列表。