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

不规则零件条带排样 · GARDEYN2 · 50 件,各不相同

给定条带高度 H、若干零件多边形及每种零件的需求份数,将全部零件放入条带中,使所有放置后顶点的最大 x 坐标(占用长度 L)最小。每份零件仅允许平移并绕自身原点旋转 0°、90°、180° 或 270°,允许边界接触但内部不得重叠,且不得越出条带。

子题GARDEYN2 · 50 件,各不相同
目标最小化 占用长度

纪录对比

占用长度 · 越小越好
纪录数值 / 区间作者 / 持有人来源
外部已知最好——暂无收录
本站纪录47298.787288135972630698zzzcy纪录详情 ↓

严格定义

  • 容器闭区域 {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
放大编辑并提交 ↗

当前展示:本站纪录

已验证构造占用长度 47298.787

帮助理解

三个工业排样实例

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,保留原始十进制顶点坐标而不做浮点截断。各子题的输入哈希与来源链接可在编辑器中下载。

查看来源
不规则零件条带排样 GARDEYN2 · 50 件,各不相同 的当前纪录构型,47298.787288135972630698
构型与历史

纪录详情

查看构型、求解笔记与纪录历史。

纪录保持者zzzcy
解题方式AI · OpenAI: GPT-6 Astra
挑战这个纪录 ↗提交证明 / 思路 ↓在讨论区分享最优性证明或关键界限思路,经审核采纳后可获证明分。
纪录保持者的求解笔记暂无求解笔记(点击展开)+

纪录保持者暂未分享求解过程。

历史纪录(25 次易主)
  1. zzzcyAI · OpenAI: GPT-6 Astra
    47317.078781130908678840260343→47298.787288135972630698
  2. TmrgAI · Z.ai: GLM 5.3
    47317.07910501718940233090746→47317.078781130908678840260343
  3. TmrgAI · Z.ai: GLM 5.3
    47317.079332062246231624714148→47317.07910501718940233090746
  4. TmrgAI · OpenAI: GPT-5.6 Sol
    47317.07946628123→47317.079332062246231624714148
  5. CJerry人工
    47317.079612548274782715402828→47317.07946628123
  6. TwiAI · DeepSeek: DeepSeek V4.1 Flash
    47317.08159754912→47317.079612548274782715402828
  7. w33dAI · OpenAI: GPT-6 Astra
    47317.08159754914→47317.08159754912
  8. w33dAI · OpenAI: GPT-6 Astra
    47319.011556089259102009236813→47317.08159754914
  9. TmrgAI · OpenAI: GPT-5.6 Sol
    47319.06580712176→47319.011556089259102009236813
  10. CJerry人工
    47319.065807200068270321935415→47319.06580712176
  11. hadsajnc人工
    47319.066007200068270321935415→47319.065807200068270321935415
  12. TmrgAI · OpenAI: GPT-5.6 Sol
    47319.1203260962078516915→47319.066007200068270321935415
  13. CCHESAI · DeepSeek: DeepSeek V4.1 Flash
    47319.120326096207860795→47319.1203260962078516915
  14. 😰人工
    47319.12032609620788→47319.120326096207860795
  15. CCHESAI · DeepSeek: DeepSeek V4.1 Flash
    47319.12877→47319.12032609620788
  16. XSsMC人工
    47319.128772091571067→47319.12877
  17. 😰人工
    47319.128772091571068→47319.128772091571067
  18. 😰人工
    47319.1287720915711→47319.128772091571068
  19. CCHESAI · DeepSeek: DeepSeek V4.1 Flash
    47319.1423822→47319.1287720915711
  20. hadsajnc人工
    47319.2123822→47319.1423822
  21. hadsajnc人工
    47319.213183→47319.2123822
  22. hadsajnc人工
    47319.215183→47319.213183
  23. hadsajnc人工
    47319.21519→47319.215183
  24. NUE_13人工
    47319.21689→47319.21519
  25. 😰人工
    47319.27→47319.21689
ANSWER FORMAT

答案怎么写

条带为 {x ≥ 0, 0 ≤ y ≤ H},其中 H 为固定材料宽度(沿竖直 y 方向),条带沿水平 x 方向向右无限延伸。每个零件多边形由精确十进制顶点给出,允许为非凸多边形。

提交 {schemaVersion: "1", problemKey: "V09", instanceId, placements},其中 instanceId 为子题实例编号(如 v09-gardeyn2-v1)。placements 为每份零件提供一个 {typeId, rotation, x, y} 对象:typeId 为零件类型编号,rotation 取 0、90、180 或 270,x 与 y 为十进制字符串(最多 24 位小数,绝对值不超过 1000000),表示先绕零件自身原点旋转再平移。每种零件出现的次数必须恰好等于其需求量,数组顺序不限。零件多边形、条带高度与需求量可在页面编辑器中下载,无需随答案提交。

当前第一名的答案

{
  "instanceId": "v09-gardeyn2-v1",
  "placements": [
    {
      "rotation": 90,
      "typeId": "t1",
      "x": "20597.285239522672782186",
      "y": "3704.710132716424141108"
    },
    {
      "rotation": 0,
      "typeId": "t11",
      "x": "25575.825818913610419258",
      "y": "4156.016826720200697309"
    },
    {
      "rotation": 0,
      "typeId": "t12",
      "x": "30540.607556149858282879",
      "y": "7269.999999900000148045"
    },
    {
      "rotation": 180,
      "typeId": "t16",
      "x": "39056.382717089349171147",
      "y": "6466.371728792365502159"
    },
    {
      "rotation": 0,
      "typeId": "t17",
      "x": "24698.188218765353667550",
      "y": "531.519722740305383013"
    },
    {
      "rotation": 180,
      "typeId": "t20",
      "x": "15166.364426922174970969",
      "y": "7401.990693812384051853"
    },
    {
      "rotation": 90,
      "typeId": "t21",
      "x": "25356.556836758711142465",
      "y": "1927.327021044721959697"
    },
    {
      "rotation": 90,
      "typeId": "t23",
      "x": "10591.221048411514857435",
      "y": "0.000000100000000000"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "0.000000100000000000",
      "y": "9169.026160995405007270"
    },
    {
      "rotation": 270,
      "typeId": "t30",
      "x": "18293.592666173077304848",
      "y": "9999.999999899999238551"
    },
    {
      "rotation": 90,
      "typeId": "t32",
      "x": "31598.985941777060361346",
      "y": "0.000000100000000000"
    },
    {
      "rotation": 180,
      "typeId": "t35",
      "x": "19679.138087727809761418",
      "y": "6891.092842492354066053"
    },
    {
      "rotation": 270,
      "typeId": "t36",
      "x": "15123.086721109270001762",
      "y": "9559.055303925015323330"
    },
    {
      "rotation": 90,
      "typeId": "t37",
      "x": "41130.734245755709707737",
      "y": "0.000000100000000000"
    },
    {
      "rotation": 270,
      "typeId": "t38",
      "x": "10330.200474349019714282",
      "y": "3922.000000099999851955"
    },
    {
      "rotation": 180,
      "typeId": "t39",
      "x": "45597.680063706640794408",
      "y": "3916.728693981073320174"
    },
    {
      "rotation": 270,
      "typeId": "t41",
      "x": "6580.086720909270297852",
      "y": "9871.924627646592853125"
    },
    {
      "rotation": 90,
      "typeId": "t42",
      "x": "21535.631338038299873006",
      "y": "1524.454889060763207453"
    },
    {
      "rotation": 0,
      "typeId": "t43",
      "x": "19141.184414998762804316",
      "y": "2697.308480418818817270"
    },
    {
      "rotation": 0,
      "typeId": "t44",
      "x": "41095.889527683240885381",
      "y": "500.109102552379738427"
    },
    {
      "rotation": 180,
      "typeId": "t45",
      "x": "32543.362881635064695729",
      "y": "8528.371320881498832023"
    },
    {
      "rotation": 180,
      "typeId": "t46",
      "x": "40190.657392093940870836",
      "y": "9975.636887520893651526"
    },
    {
      "rotation": 0,
      "typeId": "t47",
      "x": "36350.155406401281652506",
      "y": "5084.501714345855361898"
    },
    {
      "rotation": 270,
      "typeId": "t48",
      "x": "27925.427734081662492827",
      "y": "1304.000000199999931283"
    },
    {
      "rotation": 90,
      "typeId": "t5",
      "x": "13439.965255014400099753",
      "y": "5221.830472884296796110"
    },
    {
      "rotation": 270,
      "typeId": "t7",
      "x": "11393.151054833126181620",
      "y": "9999.999999899999238551"
    },
    {
      "rotation": 0,
      "typeId": "t9",
      "x": "33056.374416793194541242",
      "y": "7232.112716057656143676"
    },
    {
      "rotation": 0,
      "typeId": "t29",
      "x": "36257.674175116146216169",
      "y": "9142.278611239877136541"
    },
    {
      "rotation": 0,
      "typeId": "t24",
      "x": "0.000000100000000000",
      "y": "8950.723303953578579240"
    },
    {
      "rotation": 90,
      "typeId": "t28",
      "x": "35993.960563943051965907",
      "y": "52.123287245728022299"
    },
    {
      "rotation": 180,
      "typeId": "t34",
      "x": "29778.200474549019418191",
      "y": "500.000000100000022485"
    },
    {
      "rotation": 90,
      "typeId": "t31",
      "x": "11593.834187198002837249",
      "y": "5400.569343160816060845"
    },
    {
      "rotation": 270,
      "typeId": "t0",
      "x": "3838.086720709271503438",
      "y": "9550.014568860495273839"
    },
    {
      "rotation": 0,
      "typeId": "t14",
      "x": "1662.539604160792350740",
      "y": "9332.334415064688073471"
    },
    {
      "rotation": 180,
      "typeId": "t22",
      "x": "26978.200474449018656742",
      "y": "1488.000000100000079328"
    },
    {
      "rotation": 0,
      "typeId": "t13",
      "x": "14272.341624057511580759",
      "y": "4429.658678086394502316"
    },
    {
      "rotation": 0,
      "typeId": "t15",
      "x": "21490.856304451284813695",
      "y": "652.504282691715275178"
    },
    {
      "rotation": 0,
      "typeId": "t40",
      "x": "30195.370487715281342389",
      "y": "8408.625913388150365790"
    },
    {
      "rotation": 180,
      "typeId": "t33",
      "x": "30195.932726817987713730",
      "y": "9999.999999899999238551"
    },
    {
      "rotation": 0,
      "typeId": "t26",
      "x": "7485.086721009270149807",
      "y": "6996.159660109459764499"
    },
    {
      "rotation": 180,
      "typeId": "t18",
      "x": "21791.377205924964073347",
      "y": "7303.638354815592720115"
    },
    {
      "rotation": 90,
      "typeId": "t19",
      "x": "37612.855456477336701937",
      "y": "6658.668847782924785861"
    },
    {
      "rotation": 90,
      "typeId": "t25",
      "x": "47013.361846917388902511",
      "y": "0.000000100000000000"
    },
    {
      "rotation": 0,
      "typeId": "t10",
      "x": "45327.988071692001540214",
      "y": "1084.444151827786299691"
    },
    {
      "rotation": 0,
      "typeId": "t27",
      "x": "46234.787288135972630698",
      "y": "1075.870429018825234380"
    },
    {
      "rotation": 0,
      "typeId": "t4",
      "x": "0.000000100000000000",
      "y": "0.000000100000000000"
    },
    {
      "rotation": 180,
      "typeId": "t8",
      "x": "6580.086720809270445898",
      "y": "9692.000002000000677072"
    },
    {
      "rotation": 270,
      "typeId": "t49",
      "x": "41126.356680876328027807",
      "y": "698.000000099999965641"
    },
    {
      "rotation": 0,
      "typeId": "t6",
      "x": "40168.787288135972630698",
      "y": "3997.999999900000148045"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "4996.539604260791747947",
      "y": "9999.999999899999238551"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "case": "gardeyn2"
}

当前第一名的答案

{
  "instanceId": "v09-gardeyn2-v1",
  "placements": [
    {
      "rotation": 90,
      "typeId": "t1",
      "x": "20597.285239522672782186",
      "y": "3704.710132716424141108"
    },
    {
      "rotation": 0,
      "typeId": "t11",
      "x": "25575.825818913610419258",
      "y": "4156.016826720200697309"
    },
    {
      "rotation": 0,
      "typeId": "t12",
      "x": "30540.607556149858282879",
      "y": "7269.999999900000148045"
    },
    {
      "rotation": 180,
      "typeId": "t16",
      "x": "39056.382717089349171147",
      "y": "6466.371728792365502159"
    },
    {
      "rotation": 0,
      "typeId": "t17",
      "x": "24698.188218765353667550",
      "y": "531.519722740305383013"
    },
    {
      "rotation": 180,
      "typeId": "t20",
      "x": "15166.364426922174970969",
      "y": "7401.990693812384051853"
    },
    {
      "rotation": 90,
      "typeId": "t21",
      "x": "25356.556836758711142465",
      "y": "1927.327021044721959697"
    },
    {
      "rotation": 90,
      "typeId": "t23",
      "x": "10591.221048411514857435",
      "y": "0.000000100000000000"
    },
    {
      "rotation": 270,
      "typeId": "t3",
      "x": "0.000000100000000000",
      "y": "9169.026160995405007270"
    },
    {
      "rotation": 270,
      "typeId": "t30",
      "x": "18293.592666173077304848",
      "y": "9999.999999899999238551"
    },
    {
      "rotation": 90,
      "typeId": "t32",
      "x": "31598.985941777060361346",
      "y": "0.000000100000000000"
    },
    {
      "rotation": 180,
      "typeId": "t35",
      "x": "19679.138087727809761418",
      "y": "6891.092842492354066053"
    },
    {
      "rotation": 270,
      "typeId": "t36",
      "x": "15123.086721109270001762",
      "y": "9559.055303925015323330"
    },
    {
      "rotation": 90,
      "typeId": "t37",
      "x": "41130.734245755709707737",
      "y": "0.000000100000000000"
    },
    {
      "rotation": 270,
      "typeId": "t38",
      "x": "10330.200474349019714282",
      "y": "3922.000000099999851955"
    },
    {
      "rotation": 180,
      "typeId": "t39",
      "x": "45597.680063706640794408",
      "y": "3916.728693981073320174"
    },
    {
      "rotation": 270,
      "typeId": "t41",
      "x": "6580.086720909270297852",
      "y": "9871.924627646592853125"
    },
    {
      "rotation": 90,
      "typeId": "t42",
      "x": "21535.631338038299873006",
      "y": "1524.454889060763207453"
    },
    {
      "rotation": 0,
      "typeId": "t43",
      "x": "19141.184414998762804316",
      "y": "2697.308480418818817270"
    },
    {
      "rotation": 0,
      "typeId": "t44",
      "x": "41095.889527683240885381",
      "y": "500.109102552379738427"
    },
    {
      "rotation": 180,
      "typeId": "t45",
      "x": "32543.362881635064695729",
      "y": "8528.371320881498832023"
    },
    {
      "rotation": 180,
      "typeId": "t46",
      "x": "40190.657392093940870836",
      "y": "9975.636887520893651526"
    },
    {
      "rotation": 0,
      "typeId": "t47",
      "x": "36350.155406401281652506",
      "y": "5084.501714345855361898"
    },
    {
      "rotation": 270,
      "typeId": "t48",
      "x": "27925.427734081662492827",
      "y": "1304.000000199999931283"
    },
    {
      "rotation": 90,
      "typeId": "t5",
      "x": "13439.965255014400099753",
      "y": "5221.830472884296796110"
    },
    {
      "rotation": 270,
      "typeId": "t7",
      "x": "11393.151054833126181620",
      "y": "9999.999999899999238551"
    },
    {
      "rotation": 0,
      "typeId": "t9",
      "x": "33056.374416793194541242",
      "y": "7232.112716057656143676"
    },
    {
      "rotation": 0,
      "typeId": "t29",
      "x": "36257.674175116146216169",
      "y": "9142.278611239877136541"
    },
    {
      "rotation": 0,
      "typeId": "t24",
      "x": "0.000000100000000000",
      "y": "8950.723303953578579240"
    },
    {
      "rotation": 90,
      "typeId": "t28",
      "x": "35993.960563943051965907",
      "y": "52.123287245728022299"
    },
    {
      "rotation": 180,
      "typeId": "t34",
      "x": "29778.200474549019418191",
      "y": "500.000000100000022485"
    },
    {
      "rotation": 90,
      "typeId": "t31",
      "x": "11593.834187198002837249",
      "y": "5400.569343160816060845"
    },
    {
      "rotation": 270,
      "typeId": "t0",
      "x": "3838.086720709271503438",
      "y": "9550.014568860495273839"
    },
    {
      "rotation": 0,
      "typeId": "t14",
      "x": "1662.539604160792350740",
      "y": "9332.334415064688073471"
    },
    {
      "rotation": 180,
      "typeId": "t22",
      "x": "26978.200474449018656742",
      "y": "1488.000000100000079328"
    },
    {
      "rotation": 0,
      "typeId": "t13",
      "x": "14272.341624057511580759",
      "y": "4429.658678086394502316"
    },
    {
      "rotation": 0,
      "typeId": "t15",
      "x": "21490.856304451284813695",
      "y": "652.504282691715275178"
    },
    {
      "rotation": 0,
      "typeId": "t40",
      "x": "30195.370487715281342389",
      "y": "8408.625913388150365790"
    },
    {
      "rotation": 180,
      "typeId": "t33",
      "x": "30195.932726817987713730",
      "y": "9999.999999899999238551"
    },
    {
      "rotation": 0,
      "typeId": "t26",
      "x": "7485.086721009270149807",
      "y": "6996.159660109459764499"
    },
    {
      "rotation": 180,
      "typeId": "t18",
      "x": "21791.377205924964073347",
      "y": "7303.638354815592720115"
    },
    {
      "rotation": 90,
      "typeId": "t19",
      "x": "37612.855456477336701937",
      "y": "6658.668847782924785861"
    },
    {
      "rotation": 90,
      "typeId": "t25",
      "x": "47013.361846917388902511",
      "y": "0.000000100000000000"
    },
    {
      "rotation": 0,
      "typeId": "t10",
      "x": "45327.988071692001540214",
      "y": "1084.444151827786299691"
    },
    {
      "rotation": 0,
      "typeId": "t27",
      "x": "46234.787288135972630698",
      "y": "1075.870429018825234380"
    },
    {
      "rotation": 0,
      "typeId": "t4",
      "x": "0.000000100000000000",
      "y": "0.000000100000000000"
    },
    {
      "rotation": 180,
      "typeId": "t8",
      "x": "6580.086720809270445898",
      "y": "9692.000002000000677072"
    },
    {
      "rotation": 270,
      "typeId": "t49",
      "x": "41126.356680876328027807",
      "y": "698.000000099999965641"
    },
    {
      "rotation": 0,
      "typeId": "t6",
      "x": "40168.787288135972630698",
      "y": "3997.999999900000148045"
    },
    {
      "rotation": 180,
      "typeId": "t2",
      "x": "4996.539604260791747947",
      "y": "9999.999999899999238551"
    }
  ],
  "problemKey": "V09",
  "schemaVersion": "1"
}

提交 {schemaVersion: "1", problemKey: "V09", instanceId, placements},其中 instanceId 为子题实例编号(如 v09-gardeyn2-v1)。placements 为每份零件提供一个 {typeId, rotation, x, y} 对象:typeId 为零件类型编号,rotation 取 0、90、180 或 270,x 与 y 为十进制字符串(最多 24 位小数,绝对值不超过 1000000),表示先绕零件自身原点旋转再平移。每种零件出现的次数必须恰好等于其需求量,数组顺序不限。零件多边形、条带高度与需求量可在页面编辑器中下载,无需随答案提交。 · 验证器 v1.0.0

DISCUSSION

讨论区

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