P81 · 装箱与覆盖 · 经典问题 · 应用前沿

不规则零件条带排样

Name: P81 — 不规则零件条带排样
Creator: MinMax Arena
License: https://creativecommons.org/licenses/by/4.0/

已验证构造占用长度 47319.411

GARDEYN2 · 50 件，各不相同当前纪录 · 打开子题

给定条带高度 H、若干零件多边形及每种的需求数量，把全部零件放入条带，使所有顶点中最大的 x 坐标 L 最小。零件只能平移并转 0°、90°、180° 或 270°，可以接触但内部不能重叠，也不能越出条带。

严格定义

容器闭区域 {x ≥ 0, 0 ≤ y ≤ H}；零件贴住边界允许。H 由子题给定：GARDEYN1 为 20000，GARDEYN2 为 10000，GARDEYN9 为 44
提交每份零件一项放置：类型、旋转角和平移量。零件的多边形（可凹、可不对称）、需求数量和条带高度由子题冻结，提交不改变任何顶点、数量或形状
运动每份零件先绕自身原点旋转 0°、90°、180° 或 270°，再平移 (x, y)。不允许镜像、缩放和任意角度
不重叠任意两份零件的内部不相交：边或顶点接触允许，包含或任何正面积的重叠都不行
精确验证坐标是最多 24 位小数的十进制串，按 10²⁴ 放大为整数；四种直角旋转保持整数。每个多边形精确三角剖分，每对三角形用 BigInt 叉积做分离轴判定；投影端点相等算接触，不算重叠。没有浮点，没有 ε
分数所有放置后顶点的最大 x 坐标 L，精确到 24 位小数；越小越好。不计源文件里的容器长度，也不接受自报分数
目标在所有合法放置中最小化 L

帮助理解

为什么是这三个实例

GARDEYN 系列来自服装裁剪和 DTF 打印的真实订单：轮廓凹凸不平、不对称，重复件不多。GARDEYN1 是 10 种零件各 5 份，GARDEYN2 是 50 件互不相同的裁片，GARDEYN9 是 47 件互不相同的打印图案、条带只有 44 高。三个子题各自完整，不能把一个的答案套到另一个上。

只准转直角

文献里的排样求解器通常允许连续旋转，但连续角度的坐标带着三角函数，无法精确验证。本题只允许 0°、90°、180°、270°，一切坐标保持有理数，验证器可以毫无容差地判定接触与重叠。这也意味着本题和允许自由旋转的公开成绩不完全可比。

前沿在哪里

没有外部纪录。Sparrow 仓库公开了它自己求出的布局（长度分别为 16181.169、47382.125、65.792223），在本题规则下均可精确验证通过；本站以此为起点做了短时的精确压紧，把三个子题分别压到 16177.649、47319.670679、65.769735999999999，作为基线署名 MinMax Arena。它们都不是最优性证明，也不是文献纪录：编辑器里可以载入 Sparrow 的布局和更弱的 20 秒起始布局来对照。

查看来源

数据来源

实例几何与参考布局取自 Sparrow 仓库（Jeroen Gardeyn、Greet Vanden Berghe、Tony Wauters，KU Leuven，MIT 许可）固定版本 649d4c78，原始十进制坐标未经浮点截断；每个子题的输入哈希与来源链接可在编辑器中下载。

查看来源

逐个 n 竞争

所有 n 的当前最佳解

每个 n 都是一道独立的子题，各有各的纪录和页面。选择任意一格查看当前构造，或提交更好的答案。

讨论区（1）↓

子题GARDEYN1 · 50 件，10 种

子题GARDEYN2 · 50 件，各不相同

子题GARDEYN9 · 47 件，各不相同

当前纪录65.769735999999999

难

答案来源MinMax Arena

解题方式本站离线搜索

引用与数据

这一题族的全部子题、权威分数、证明状态、坐标与来源，都在下面这个稳定地址里，以 CC BY 4.0 发布。分数会随纪录变化，引用时请一并记录文件里的 generatedAt。

GET https://minmaxarena.com/data/irregular-strip-nesting.json

引用请指向 2026-08 冻结版：纪录会变，冻结版永远不变，所以引文十年后仍可核对。

GET https://minmaxarena.com/data/editions/2026-08/irregular-strip-nesting.json

BibTeX（点开复制）

@misc{minmaxarena-irregular-strip-nesting-2026-08,
  title  = {{Irregular strip nesting} (P81)},
  author = {{MinMax Arena}},
  year   = {2026},
  note   = {Machine-verified records, 2026-08 edition},
  url    = {https://minmaxarena.com/data/editions/2026-08/irregular-strip-nesting.json},
  license = {CC BY 4.0}
}

DISCUSSION

讨论区

聊思路、贴方法、问为什么卡住。所有登录用户都可以发帖；发言公开署名，与纪录使用同一个名字，署名后的 #编号是账号注册序号，冒不了名。新发言经自动审核后公开。

问题大草NUE_13#310 条回复55 分钟前