草庐IT

javascript - 一维阵列 - 以最少的浪费确定最佳容器尺寸

coder 2024-07-20 原文

编辑:感谢 Alain 对此的正确描述:

问题是这样的:一家商店试图找到其纸板箱的最佳尺寸，以便能够包装所有商品，并尽量减少纸箱中的浪费空间。

目前我有一个包含卷的数据集。我需要弄清楚例如我可以使用的容器数量是否为 5 个，适合所有这些体积的 5 个最佳尺寸是多少？例如，这个数组包含我的卷:

var numbers =[10, 20, 20, 30, 50, 50, 50, 80];

为了简单起见，我有 2 个容器。大小分别为 50 和 80。

10装50，废40，20装50，废30等等。 50 适合 50，但浪费为 0。同样适用于 80。总共浪费为 120。

但是如果尺寸不同呢？ 60 和 80。那么总的浪费就是 180。

(60-10) + (60-20) + (60-20) + (60-30) + (60-50) + (60-50) + (60-50) + (80-80)

我的问题是，确定容器大小的最有效方法是什么？假设您知道可以使用的容器数量和数组中的数字(在本例中为体积)。

例如，如果我不知道我的容器的大小应该是 50 和 80 怎么办？如果我只知道我可以使用多少个容器以及每个对象的体积是多少，我将如何计算出最佳的正确大小？

是否有某种算法，如果有，您能举个例子吗？我试着查找像 bin packing、knapsack 和 k-means 这样的东西，但我不太清楚如何将它们应用到这个问题上。我只想计算哪种尺寸最适合存储所有卷，同时浪费最少。

我希望我对这个例子很清楚，如果不明白请询问更多。提前致谢。

最佳答案

我的方法是将数组转换为一个集合以删除重复项，然后转换回数组以便对其进行排序。然后颠倒顺序，让我们有最大的好东西在前面。至此，预处理步骤完成。

下一步是声明容器可用性，您可以查看代码并根据需要进行修改，在我的示例中，我将使用 3 个容器(或纸板箱)。我修改了数组来测试一些情况。

遍历您创建的反向数组，如果容器大小不等于当前的好东西大小并且您仍然有可用的容器大小，则减少 1 个容器大小可用性并将大小推送到容器列表。一旦您没有要检查的容器大小，我就尝试和捕获只是为了中断迭代。最后，用我们得到的最小容器填充 goodies 数组的其余部分。

此算法的复杂度为 O(容器数量_avail + 数量 remaining_goodies)[基本上，O(n)]。

var numbers = [60, 40, 20, 20, 10, 50, 50, 50, 80];
var original_numbers_length = numbers.length;
console.log('Given unsorted goodies: ', numbers);
numbers = new Set(numbers);
numbers = Array.from(numbers)
numbers.sort();
numbers.reverse();

var container_avai = 3;
var container_size = 0;
var container_list = [];

console.log('All goodies: ', numbers);
console.log('Given container available: ', container_avai);

var BreakException = {}

try{
    numbers.forEach(function(item){
    if( container_size != item && container_avai > 0){
        container_avai -= 1;
        container_size = item;
        container_list.push(container_size);
    }
    if ( container_avai == 0){
        throw BreakException;
    }
});}
catch (e) {
    // Done
}
remaining_goodies = original_numbers_length - container_list.length;
smallest_container = container_list[container_list.length - 1];

for (i = 0; i < remaining_goodies; i++){
    container_list.push(smallest_container);
}

console.log('Appropriate containers are: ', container_list);

我得到的输出:

Given unsorted goodies:  [ 60, 40, 20, 20, 10, 50, 50, 50, 80 ]
All goodies:  [ 80, 60, 50, 40, 20, 10 ]
Given container available:  3
Appropriate containers are:  [ 80, 60, 50, 50, 50, 50, 50, 50, 50 ]

希望这对您有所帮助。

关于javascript - 一维阵列 - 以最少的浪费确定最佳容器尺寸，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45105249/

容器javascriptcontainernumbersarraysalgorithmcontainers

有关javascript - 一维阵列 - 以最少的浪费确定最佳容器尺寸的更多相关文章

  1. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  3. ruby - 即时确定方法的可见性 - 2

    我正在编写一个方法，它将在一个类中定义一个实例方法；类似于attr_accessor:classFoocustom_method(:foo)end我通过将custom_method函数添加到Module模块并使用define_method定义方法来实现它，效果很好。但我无法弄清楚如何考虑类(class)的可见性属性。例如，在下面的类中classFoocustom_method(:foo)privatecustom_method(:bar)end第一个生成的方法(foo)必须是公共(public)的，第二个(bar)必须是私有(private)的。我怎么做？或者，如何找到调用我的cust

  4. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  5. ruby - 确定 ruby​​ 脚本是否已经在运行 - 2

    有没有一种简单的方法可以判断ruby​​脚本是否已经在运行，然后适本地处理它？例如:我有一个名为really_long_script.rb的脚本。我让它每5分钟运行一次。当它运行时，我想看看之前运行的是否还在运行，然后停止第二个脚本的执行。有什么想法吗？ 最佳答案 ps是一种非常糟糕的方法，并且可能会出现竞争条件。传统的Unix/Linux方法是将PID写入文件(通常在/var/run中)并在启动时检查该文件是否存在。例如pid文件位于/var/run/myscript.pid然后你会在运行程序之前检查它是否存在。有一些技巧可以避免

  6. ruby-on-rails - Rails 中同一个类的多个关联的最佳实践？ - 2

    我认为我的问题最好用一个例子来描述。假设我有一个名为“Thing”的简单模型，它有一些简单数据类型的属性。像...Thing-foo:string-goo:string-bar:int这并不难。数据库表将包含具有这三个属性的三列，我可以使用@thing.foo或@thing.bar之类的东西访问它们。但我要解决的问题是当“foo”或“goo”不再包含在简单数据类型中时会发生什么？假设foo和goo代表相同类型的对象。也就是说，它们都是“Whazit”的实例，只是数据不同。所以现在事情可能看起来像这样......Thing-bar:int但是现在有一个新的模型叫做“Whazit”，看起来

  7. ruby-on-rails - 向 Rails 3 添加 Ruby 扩展方法的最佳实践？ - 2

    我有一个要在我的Rails3项目中使用的数组扩展方法。它应该住在哪里？我有一个应用程序/类，我最初把它放在(array_extensions.rb)中，在我的config/application.rb中我加载路径:config.autoload_paths+=%W(#{Rails.root}/应用程序/类)。但是，当我转到railsconsole时，未加载扩展。是否有一个预定义的位置可以放置我的Rails3扩展方法？或者，一种预先定义的方式来添加它们？我知道Rails有自己的数组扩展方法。我应该将我的添加到active_support/core_ext/array/conversion

  8. ruby - 最佳原则中的原则 - 2

    我似乎经常遇到一些设计问题，但我不知道是什么是真的很合适。一方面我经常听到我应该限制耦合和坚持单一职责，但当我这样做时，我常常发现它很困难到在需要时将信息获取到程序的一部分。为了例如，classSingerdefinitialize(name)@name=nameendattr:nameend那么Song应该是:classSongdefnew(singer)@singer=singerendend或classSongdefnew(singer_name)@singer_name=singer_nameendend后者耦合性小，按道理应该用。但如果我以后发现宋有什么需要了解更多歌手，我的

  9. ruby-on-rails - 使用 javascript 更改数据方法不会更改 ajax 调用用户的什么方法？ - 2

    我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的

  10. ruby - 确定字符串的结尾是否与单独的字符串的开头重叠 - 2

    我想查找字符串的结尾是否与单独字符串的开头重叠。例如，如果我有这两个字符串:string_1='Peoplesaynothingisimpossible,butI'string_2='butIdonothingeveryday.'如何找到string_1末尾的“butI”部分与string_2开头相同？我可以编写一个方法来遍历这两个字符串，但我希望得到一个包含我错过的Ruby字符串方法或Ruby习惯用法的答案。 最佳答案 将MARKER设置为一些从未出现在您的string_1和string_2中的字符串。有一些方法可以动态地做到这一

随机推荐