将对象数组拆分为多个“桶”。

问题描述 投票:0回答:1

我认为这就像 CompSci 101,但我从未参加过正式的编码课程。我只是一名通过经验自学的管理员。我更喜欢从尽可能接近“从头开始”的地方自己解决问题,但事实证明,这对我平庸的智商来说有点令人困惑,我希望得到一些帮助。我脑子里好像有一个……椒盐卷饼。

我最近一直在思考如何有效地将一组对象(每个对象都有不同大小的数值)排列到尽可能数量的固定大小的“桶”中。就像我有 1,000 个 1-100 之间的值实例,我想弄清楚如何将它们排列到最少数量的桶中,假设每个桶中的值之和(不是对象的数量)不能超过 100 或 200 ,或任何大小。不仅仅是我需要多少个桶。这就像一年级或二年级的数学。

如果我解释得不够好,请想一个这样的问题。 UPS 有 100,000 个包裹。每个重量从 1 到 100 磅不等,您知道每个重量有多少。每辆 UPS 卡车可运载 10,000 磅。哪些包裹应该装到哪些卡车上,以尽量减少所需的卡车数量?不,我不为 UPS 工作。这只是我想到的第一个类比。是的,我知道在这个类比中我低估了数量。这不是专门针对工作、课程或测试的。最近它一直困扰着我,让我觉得自己很愚蠢。

我过去做过一些事情。它们都感觉相当“贫民窟”且不精确,但是当我想要批处理对象并分发它们的处理而不是在单个数组上使用简单的串行循环时,它们对我来说很容易理解,可以快速编码,并且可以更快地执行。对象在一个地方执行。

我已按降序值对对象进行排序,根据适合任务的任何标准决定存储桶大小和数量,然后迭代数组,按顺序将每个对象分配到下一个存储桶,在运行时回绕到第一个存储桶出桶。如果我将 1-100 的精确值排序到 3 个桶中,则 100 放入桶 1,99 放入桶 2,98 放入桶 3,97 放入桶 1,依此类推。

我还选择了一个存储桶大小,并迭代分配给当前存储桶的数组,直到其容量耗尽,然后为下一个对象创建一个新存储桶,同时还检查每个当前对象上的每个先前存储桶以查看是否有一个在为其创建新存储桶之前,其中有足够的剩余容量来容纳它。

以及这些的一些变化和组合。

我并不是真的在寻找一个完全编码的特定于语言的解决方案(我认为我对 PowerShell 和 JavaScript 有一定的能力),也不是想得到“答案”。我正在寻找关于如何解决此类问题的高级概述或一些指导,以使我的灯泡足够亮以自行完成。这似乎是一个很常见的问题,但我在搜索时使用的措辞并没有找到任何接近我想要完成的目标的东西。

algorithm powershell logic
1个回答
0
投票

您在抽象中描述的一系列问题更常见的是“装箱问题”,您的具体约束描述了我们所谓的“最小装箱实例包装问题” - 必须包装一组有限的项目将不同尺寸的垃圾箱放入一组尽可能小的垃圾箱中,每个垃圾箱都有给定的最大容量。

您描述的所有尝试听起来都像所谓的first-fit算法 - 正如您可能发现它们可以相对有效地实现(在计算和源代码复杂性方面),但有时最终会产生子- 最佳包装分布,这意味着您最终会使用比您可以拥有的更多的垃圾箱/桶。 装箱与其他广义装箱问题密切相关,例如

背包问题的 0-1 变体

- 从技术上讲,装箱问题的最大装箱数为 1。

© www.soinside.com 2019 - 2024. All rights reserved.