题库PACKING PROBLEMS

装箱问题

把若干个物体塞进一个容器,不许重叠,让它们尽可能大或尽可能多。这一页收录本站全部装箱题族:每个分数由确定性验证器精确复算,每个已知值都注明来源与是否已被证明。

题族17
子题351
仍然开放285

什么是装箱问题

一个装箱问题固定三样东西:装什么(等大的圆、大小各异的圆、可倾斜的正方形、过原点的直线)、装进哪里(正方形、圆、L 形、十字、半圆、扇形、直角三角形),以及要最大化什么(共同半径、半径之和、共同边长、最小夹角)。三样都固定之后,剩下的就是排布本身——而对绝大多数参数,最优排布至今没人知道。

这就是装箱问题在计算机时代仍然活跃的原因:验证一个排布很容易,找到最好的排布很难。本站正是围绕这个不对称建起来的——任何人都能提交坐标,验证器在毫秒内用整数算术给出精确分数,比现有纪录好就立刻公开留名。

装箱、覆盖、散布与能量

装箱要求互不重叠,最大化尺寸;覆盖要求不留空隙,最小化尺寸;散布问题不放实体、只放点,最大化点之间的最小距离;能量问题最小化一个对所有点对求和的势函数。四类题目常被混为一谈,但目标函数完全不同,最优构型也不同。本站四类都有,这一页只列装箱。

“可验证”在这里的确切含义

每份提交都是一组九位小数坐标。验证器把它们读成整数,用 BigInt 判断越界与重叠——不取浮点、不开平方、不比较近似值。因此同一份证书在任何机器上得到同一个分数,纪录不依赖谁的显卡更快。

已知值分两种,页面从不混用:“已证明最优”意味着有人证明了没有更好的排布,达到它这道子题就此完结;“最好已知”只是目前无人超越,追平算持平,超越就是一项真实成果。每个引用值都附出处链接。

P02 · 单位圆内的等圆装箱 · n = 19
P10 · 等圆装入十字形 · n = 12
P57 · 正方形内圆的半径之和 · n = 19

等圆与自由圆

最经典的一族:把 n 个圆塞进一个固定容器,让共同半径最大;P57 放开了“等大”这一条,改成最大化半径之和。

P01 · 单位正方形内的等圆装箱放置 n 个等圆,使共同半径尽可能大。
30 个子题 · 0 个开放 · 30 个已完结 · 30 个有已知值
P02 · 单位圆内的等圆装箱在单位圆内放置 n 个互不相交的等圆。
29 个子题 · 15 个开放 · 14 个已完结 · 28 个有已知值
P08 · 等圆装入 L 形在一个 L 形区域内放 n 个等圆,使共同半径尽可能大。
15 个子题 · 15 个开放 · 0 个已完结 · 0 个有已知值
P09 · 等圆装入半圆在半径 1 的半圆内放 n 个等圆,使共同半径尽可能大。
14 个子题 · 14 个开放 · 0 个已完结 · 14 个有已知值
P10 · 等圆装入十字形在一个十字形区域内放 n 个等圆,使共同半径尽可能大。
16 个子题 · 16 个开放 · 0 个已完结 · 0 个有已知值
P11 · 直角三角形内的等圆装箱在直角边为 1 与 0.75 的固定直角三角形内放置 n 个互不相交的等圆,使共同半径尽可能大。
11 个子题 · 11 个开放 · 0 个已完结 · 0 个有已知值
P12 · 2:1 长方形内的等圆装箱在 2×1 的长方形内放置 n 个互不相交的等圆,使共同半径尽可能大。
10 个子题 · 6 个开放 · 4 个已完结 · 4 个有已知值
P30 · 等圆装入扇形在半径 1 的扇形(四分之一圆)内放 n 个等圆,使共同半径尽可能大。
14 个子题 · 14 个开放 · 0 个已完结 · 14 个有已知值
P57 · 正方形内圆的半径之和在单位正方形内放 n 个互不重叠的圆,大小随意,使所有半径之和尽可能大。
30 个子题 · 29 个开放 · 1 个已完结 · 2 个有已知值

半径 1…n 的圆

圆的大小由题目固定为 1, 2, …, n,可变的是容器:把它缩到最小。

可倾斜的正方形

每个正方形可以任意转角,这让搜索空间从位置扩大到位置加姿态,也是这一族至今大量参数未解的原因。

高维与抽象空间

装的不再是平面上的图形,而是方向、直线、平面:这些题目的分数同样由精确整数算术给出,前沿则直接对着 Sloane 的打包表。

最新突破

周报 · 题库

取用数据

每个题族都有一个稳定的 JSON 地址,包含全部子题的权威分数、证明状态、坐标、来源与验证器版本:

GET https://minmaxarena.com/data/square-circle-packing.json

数据以 CC BY 4.0 发布:随便用,注明来源并链接回本站即可。分数会随纪录变化,所以引用时请一并记录文件里的 generatedAt 时间戳。