- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我们有一大堆机器使用一大堆数据存储。我们想将所有机器的数据传输到新的数据存储中。这些新商店的机器可用存储空间量各不相同。此外,每台机器需要存储的数据量各不相同。单个机器的所有数据必须存储在单个数据存储中;它不能被分割。除此之外,数据的分配方式并不重要。
我们目前拥有的数据多于我们的空间,因此不可避免地,某些机器需要将数据保留在原处,直到我们找到更多数据。与此同时,有没有人知道一种算法(相对简单:我没那么聪明)可以为我们拥有的存储提供最佳或接近最佳的分配(即分配后新存储上剩余的空间最少) )?
我知道这听起来像是一道家庭作业题,但我向你保证这是真的!
最佳答案
乍一看这似乎是多背包问题(http://www.or.deis.unibo.it/knapsack.html,第 6.6 章“多背包问题 - 近似算法”),但实际上它是一个调度问题,因为它涉及时间元素。不用说,解决这些类型的问题很复杂。一种方法是将它们建模为网络流并使用像 GOBLIN 这样的网络流库。
在您的情况下,请注意您实际上不想以最佳方式填充存储,因为如果您这样做,将更有可能存储较小的数据包,因为它会导致更紧密的包装。这很糟糕,因为如果大包裹留在机器上,那么您 future 的包装会越来越糟糕。您想要做的是优先存储较大的包裹,即使这意味着在商店中留出更多额外空间,因为这样您将来会获得更大的灵 active 。
下面是如何用一个简单的算法解决这个问题:
(1) 确定 bin 大小并对它们进行排序。例如,如果您有 3 家商店,空间分别为 20 GB、45 GB 和 70 GB,那么您的目标是 { 20, 45, 70 }。
(2) 将所有数据包按大小排序。例如,您可能有数据包:{ 2, 2, 4, 6, 7, 7, 8, 11, 13, 14, 17, 23, 29, 37 }。
(3) 如果任何包裹的总和超过商店的 95%,则将它们放入该商店并转到步骤 (1)。这里不是这种情况。
(4) 生成两个包的所有排列。
(5) 如果任何排列总和大于商店的 95%,则将它们放入该商店。如果有领带,则更喜欢带有更大包装的组合。在我的示例中,有两个这样的对 { 37, 8 } = 45 和 { 17, 2 } = 19。(请注意,使用 { 17, 2 } 胜过使用 { 13, 7 })。如果找到一个或多个匹配项,请返回步骤 (1)。
好的,现在我们只剩下一家商店:70 个和以下包裹:{ 2, 4, 6, 7, 7, 11, 13, 14, 23, 29 }。
(6) 将 perms 的数量增加 1,然后转到步骤 5。例如,在我们的例子中,我们发现没有 3-perm 增加到 70 的 95% 以上,但是 4 perm { 29, 23, 14 , 4 } = 70。最后我们在机器上留下了包 { 2, 6, 7, 7, 11, 13 }。请注意,这些大多是较小的包。
请注意,perms 是按相反的词法顺序(最大的在前)进行测试的。例如,如果您有“abcde”,其中 e 是最大的,那么 3-perms 的反向词法顺序是:
cde
bde
阿德
公元前
王牌
等
此算法非常简单,并且会根据您的情况产生良好的结果。
关于algorithm - 简单的存储分配算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12828711/
我有一个应用程序,它会抛出 GKSession 并在各种条件下(连接超时、 session 失败等)创建一个新的 GKSession。不过,我遇到了内存泄漏问题,并且有时会在重新连接几次循环后崩溃。
比如我在宿主代码中有一个浮点指针 float *p 是否可以确定他指向的内存类型(设备/主机)? 最佳答案 在 UVA system 中, 运行时 API 函数 cudaPointerGetAttri
我已将项目转换为 .Net 4.0 并且以下代码不起作用: typeof(RuntimeTypeHandle).GetMethod("Allocate", BindingFlags.Instance
当我声明 char ch = 'ab' 时,ch 只包含 'b',为什么它不存储 'a'? #include int main() { char ch = 'ab'; printf("%c"
我对 Disk Sector 和 Block 有疑问。扇区是一个单位,通常为 512 字节或 1k、2k、4k 等取决于硬件。文件系统 block 大小是一组扇区大小。 假设我正在存储一个 5KB 的
假设我有 8 个人和5000 个苹果。 我想将所有苹果分发给所有 8 个人,这样我就没有苹果了。 但每个人都应该得到不同数量 将它们全部分发出去的最佳方式是什么? 我是这样开始的: let peopl
我正在构建的网站顶部有一个搜索栏。与 Trello 或 Gmail 类似,我希望当用户按下“/”键时,他们的焦点就会转到该搜索框。 我的 JavaScript 看起来像这样: document.onk
我有一小段代码: if (PZ_APP.dom.isAnyDomElement($textInputs)){ $textInputs.on("focus", function(){
我观察到以下行为。 接受了两个属性变量。 @property (nonatomic, retain) NSString *stringOne; @property (nonatomic, assign
我正在解决这样的问题 - 实现一个计算由以下内容组成的表达式的函数以下操作数:“(”、“)”、“+”、“-”、“*”、“/”。中的每个数字表达式可能很大(与由字符串表示的一样大)1000 位)。 “/
我有一组主机和一组任务。 每个主机都有 cpu、mem 和任务容量,每个任务都有 cpu、mem 要求。 每个主机都属于一个延迟类别,并且可以与具有特定延迟值的其他主机通信。 每个任务可能需要以等于或
该程序的作用:从文件中读取一个包含 nrRows 行和 nrColomns 列的矩阵(二维数组)。矩阵的所有元素都是 [0,100) 之间的整数。程序必须重新排列矩阵内的所有元素,使每个元素等于其所在
世界!我有个问题。今天我尝试创建一个代码,它可以找到加泰罗尼亚语号码。但是在我的程序中可以是长数字。我找到了分子和分母。但我不能分割长数字!此外,只有标准库必须在此程序中使用。请帮帮我。这是我的代码
我确定我遗漏了一些明显的东西,但我想在 Objective C 中创建一个 NSInteger 指针的实例。 -(NSInteger*) getIntegerPointer{ NSInteger
这个问题在这里已经有了答案: Difference between self.ivar and ivar? (4 个答案) 关闭 9 年前。
我如何将 v[i] 分配给一系列整数(v 的类型是 vector )而无需最初填充 最佳答案 你的意思是将 std::vector 初始化为一系列整数? int i[] = {1, 2, 3, 4,
我想寻求分配方面的帮助....我把这个作业带到了学校......我必须编写程序来加载一个 G 矩阵和第二个 G 矩阵,并搜索第二个 G 矩阵以获取存在数第一个 G 矩阵的......但是,当我尝试运行
我必须管理资源。它基本上是一个唯一的编号,用于标识交换机中的第 2 层连接。可以有 16k 个这样的连接,因此每次用户希望配置连接时,他/她都需要分配一个唯一索引。同样,当用户希望删除连接时,资源(号
是否有任何通用的命名约定来区分已分配和未分配的字符串?我正在寻找的是希望类似于 us/s 来自 Making Wrong Code Look Wrong ,但我宁愿使用常见的东西也不愿自己动手。 最佳
我需要读取一个 .txt 文件并将文件中的每个单词分配到一个结构中,该结构从结构 vector 指向。我将在下面更好地解释。 感谢您的帮助。 我的程序只分配文件的第一个字... 我知道问题出在函数 i
我是一名优秀的程序员,十分优秀!