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

不规则零件条带排样

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

给定条带高度 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 份（共 50 件），GARDEYN2 为 50 件互不相同的裁片，GARDEYN9 为排入高度 44 条带内的 47 件不同印花图案。

90° 离散旋转与有理数验证

排样文献中的启发式求解器有时允许连续旋转，但任意角度的三角函数会使顶点坐标脱离有理数域，难以实施无容差验证。本题限定 0°、90°、180°、270° 四种旋转，使全部顶点保持精确十进制有理数，从而支持零容差的接触与重叠判定。

Sparrow 参考布局与基线

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 都是一个独立计分的子题。点击任意卡片可查看当前纪录构型，或打开编辑器提交更优解答。

讨论区（4）↓

子题GARDEYN1 · 50 件，10 种

当前纪录16052.54859406119588349420966

难

纪录保持者邱仲普

解题方式AI · OpenAI: GPT-5.6 Sol

子题GARDEYN2 · 50 件，各不相同

当前纪录47298.787288135972630698

难

纪录保持者zzzcy

解题方式AI · OpenAI: GPT-6 Astra

子题GARDEYN9 · 47 件，各不相同

当前纪录65.66321416511283334

难

纪录保持者zzzcy

解题方式AI · OpenAI: GPT-6 Astra

引用与数据

该题族所有子题的权威分数、证明状态、坐标数据与文献来源均汇总于下方稳定链接，按 CC BY 4.0 协议发布。由于分数随纪录刷新而更新，引用时请同时注明文件中的 generatedAt 时间戳。

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

引用建议使用 2026-10 冻结归档版：实时纪录会变，但冻结版永久固定，便于日后核查。

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

BibTeX（点击复制）

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

DISCUSSION

讨论区

欢迎交流解题思路、分享构造方法或探讨卡壳之处。所有登录用户均可发帖；发言使用与排行榜一致的公开署名，并附带唯一注册编号（#UID）以防冒名。新发言经审核后公开。

第一题大概已经最优解了吧XSsMC#2506 条回复44 天前 精度太高了也是个很麻烦的问题啊Tmrg#342 条回复49 天前 可能是有史以来对AI最不友好的题目NUE_13#314 条回复50 天前 问题大草NUE_13#310 条回复51 天前