问题标签 [packing]

编辑：这个问题似乎被称为“切割库存问题”

我需要一种算法，它可以为我提供箱中块的（空间）最佳排列。一种方法是先放入较大的块。但是看看这个算法在这个例子中是如何失败的：

“最大的优先”不适合 DD。也许它有助于建立这样的表：

因此，我正在尝试实现一种算法，该算法将多个矩形作为输入，并尝试将它们打包成一个最小面积的矩形。矩形都可以旋转 90 度。

我意识到这类似于装箱问题，但我无法找到一个很好的算法来解释旋转。我在这里找到了一篇详细讨论这个问题的论文，虽然我理解这篇文章本身，但我希望能找到更简单的东西。

有什么建议么？

-编辑-

我想我之前错误地陈述了这个问题。我们得到了许多矩形，每个矩形都可以旋转 90 度。我们需要找到一个适合所有给定矩形的矩形，使得没有两个矩形重叠，同时最小化封闭矩形的面积。

我在这里面临的问题是我们被要求找到最小值，而不是给定一个封闭的矩形并检查给定的矩形是否适合或类似的东西。

I'm trying to figure out how to detect whether a binary has been compressed with UPX. I am using a simple CRC to detect whether my app was in any way changed and if the CRC failed on the size due to a packer I would like to detect that as OK.

Right now I am starting with UPX.

So, is there any marker on the binary? are there any specific JMP or other instructions that I should search?
This will mainly be tested in Windows, but in the future I might add it to Linux as well.

Any help (and code) is appreciated.

ADDED:

I found that in the 10 binaries I checked the

AddressOfEntryPoint
Import Directory RVA
Resouce Directory RVA

either point to UPX or have an offset that is set by UPX. Any information on this?

Thanks

假设我有一个完整的无向图 G，其距离与每条边相关联。长度为 l 的边 (u, v) 的含义是“点 u 和 v 不能比 l 更接近”。我的目标是将这个图的节点放在一个平面上，这样就不会违反这些距离约束，并且点的凸包的总面积最小。举个例子，假设我有一堆电子元件想放在一个芯片上，每个元件都会产生一定量的电子干扰。如果我将组件放在一起太近，它们就会开始相互干扰，从而使整个系统变得毫无用处。给定每个点与其他点之间的最小距离，将组件放置在芯片上的最节省空间的方法是什么？

我什至不知道如何开始考虑这个问题。我也不知道问题如何推广到更高维的情况（将点打包到超平面中）。有谁知道解决这个问题的好方法？

我正在编写一个着色器（HLSL），我需要将一个颜色值打包成 R32 格式。我找到了将浮点数打包成 R8G8B8A8 格式的各种代码，但它们似乎都没有反向工作。我的目标是 SM3.0，所以（afaik）位操作不是一个选项。

总结一下，我需要能够做到这一点：

有人知道怎么做吗？

更新
我已经取得了一些进展......也许这将有助于澄清这个问题。
我的临时解决方案是这样的：

我基本上......假装我正在使用整数类型：s
通过猜测和检查，64 是我可以使用的最高数字，同时仍保持 [0...1] 范围。不幸的是，这也意味着我失去了一些精度——6位而不是8位。

只是为了好玩和咯咯笑，我试图在 delphi中创建一个64k 的介绍。Farbrausch的 kkrunchy是这种规模应用程序的最佳可执行打包程序之一。但是，当我在（否则为空的）Delphi 可执行文件上运行它时，我得到以下输出

我猜 Delphi 可执行文件两者都可能是罪魁祸首，我没有真正的麻烦投入大量时间试图找出它是哪一个并发布修改可执行文件或类似的东西......但也许你们中的一个已经知道，甚至有一些关于如何规避这个问题的信息？

获取数据成员的偏移量就像这样简单：

我想让它成为一个常量编译时表达式（或使用类型特征）。例如，要使用它来实现使用成员偏移量的基于 SFINAE 的解决方案，使用它静态断言等。

更新：问题是 - 如何使其成为编译时表达式。不是它是否适用于 POD 类型，或者 C 库中是否有标准宏等。

我有一堆大小可变的矩形，我需要将它们大致组合成一个圆圈，大概最大的矩形在中心。

注意。圆圈的大小不是固定的——这只是我所追求的整体形状。

这更像是我想象的懒惰的人类包装（一旦一块到位，它就会留下来。）

它们已经按照宽度和高度的最大值排序，最大的在前。

理想情况下 - 我认为这可以通过订购来保证 - 根本不会有差距。

我正在努力的算法是：

这对于前几个矩形来说没问题，但是边缘合并非常麻烦，而且我目前选择使用边缘的哪一部分（一端或另一端）的方法往往会留下很多间隙。

尽管我认为我最终会让这种方法相当令人满意地工作，但感觉就像我缺少一种更优雅的（图形？）算法。

我的问题与 2D Knapsack 问题或切割库存非常相似，但有一个例外......适合容器的矩形可以调整大小和裁剪。但不允许旋转。

挑战在于尽可能少地生产作物并填满整个容器（没有任何间隙）。

有没有人遇到过可以做类似事情的算法。任何链接，伪代码非常感谢。

保持问题通用，但我想将其应用于在固定大小的页面上组织照片。

非常感谢

目前 ZMI 管理“打包数据库”的功能有点粗糙。

1) 是否有可能为 Web UI 提供某种进度指示器？例如，告诉您还剩多少分钟/小时，至少给出某种估计

2) ZODB 打包如何影响站点的响应性？所有交易都被阻止了吗？

3) 任何带有进度指示器的命令行脚本可用，以便您可以从 ZEO 命令行客户端执行此操作？

4) 至少有某种日志标记来注销输出... [INFO] 30% 完成... 3:15 开始