3D装箱堆叠问题
由于业务，需要装柜逻辑，之前用的装柜逻辑就是装柜专家这个逻辑，不得不说这个小软件还是可以的。
研究完这个软件后就去了解这个三维装箱，好家伙不了解不知道，这么难搞；（三维装箱问题也是NP-hard问题。由于此原因，很多之前的研究都集中于近似算法和启发式算法）；博主想都没想直接搬出了gpt 5pro。
我直接开问，然后回答
我下面给你一个实用、可落地的 3 维装箱（3D Bin Packing）算法方案，外加一份可直接运行的 Python 参考实现。它基于业界常用的极点法（Extreme-Point Placement, EP）+ 体积降序启发式：效果稳定、实现相对简单，适合从几十到数百个箱件的工程场景。
然后直接给我拉了托大的，直接暴毙，细节就不描述了；
由于，业务是java开发的就去了解，在java上有没有什么解决方案；然后还真有：
- 3d-bin-container-packing 基于 Largest Area Fit First (LAFF) 的三维实现 + 小规模场景下的穷举（支持截止时间），计算时间短且稳定，效果“够好”。
- bin-packing 3D 容器打包，基于 LAFF，追求“较快 + 还不错的利用率”。适合研究或二开参考
当然gpt还提供了别的方案比如java+求解器等等
使用3d-bin-container-packing（LAFF 启发式）
省流版：最后效果还是不行
安装依赖
<dependency>
<groupId>com.github.skjolber.3d-bin-container-packing</groupId>
<artifactId>core</artifactId>
<version>3.0.11</version>
</dependency>
具体的代码
import com.github.skjolber.packing.api.*;
import com.github.skjolber.packing.core.*;
import java.util.*;
public class DemoLaff {
public static void main(String[] args) {
// 1) 待装物品（支持数量与3D旋转）
List<StackableItem> items = List.of(
new StackableItem(Box.newBuilder().withId("A").withSize(4,3,2).withRotate3D().withWeight(10).build(), 2),
new StackableItem(Box.newBuilder().withId("B").withSize(6,2,2).withRotate3D().withWeight(8).build(), 1)
);
// 2) 容器（可配置空重/载重上限）
Container bin = Container.newBuilder()
.withDescription("Bin-1")
.withSize(10,5,5)
.withEmptyWeight(1)
.withMaxLoadWeight(100)
.build();
List<ContainerItem> bins = ContainerItem.newListBuilder().withContainer(bin).build();
// 3) 选择打包器（LAFF；也可换 BruteForce / Plain）
Packager packager = LargestAreaFitFirstPackager.newBuilder().build();
// 4) 执行与结果
PackagerResult result = packager.newResultBuilder()
.withContainers(bins)
.withStackables(items)
.withMaxContainerCount(1)
.build();
System.out.println("Success = " + result.isSuccess());
}
}
对应库与用法见其 README 与 Maven 条目（3.x 版本）。GitHubMaven Repository
然后这个虽然可以顺利的得到结果但是得到结果还是不尽如人意。
当然还有种OR‑Tools，我没去试，这个依赖装了版本不对，一直没成功；
成功了！
成功的时候居然还不是我写的代码，是gpt-5pro自己算出来了，他自己算出来了，后来我还不太相信，让他写个网页可视化一下
image.png
你还别说，这就成了！和装柜专家的装箱图都一模一样；
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width,initial-scale=1" />
<title>3D 装箱可视化（教学版：分层平面图 + 悬停坐标）</title>
<link rel="icon" href="data:,">
<style>
:root{ --bg:#0f1216; --panel:rgba(15,18,22,.75); --line:#2b3440; --txt:#e5e7eb; --muted:#9aa4b2; }
html,body{height:100%;margin:0;background:var(--bg);color:var(--txt);font:14px/1.5 system-ui,-apple-system,Segoe UI,Roboto,Arial}
#app{position:fixed;inset:0}
.sidebar{
position:absolute;left:12px;top:12px;z-index:10;display:flex;gap:12px;flex-wrap:wrap;align-items:flex-start
}
.card{
background:var(--panel);border:1px solid rgba(255,255,255,.08);border-radius:12px;padding:10px 12px;box-shadow:0 10px 30px rgba(0,0,0,.25)
}
.card h2{margin:0 0 8px;font-size:14px}
.row{display:flex;gap:10px;align-items:center;margin:6px 0}
select,input[type="checkbox"],button{accent-color:#8ab4f8}
.stats table{border-collapse:collapse;width:100%}
.stats td{padding:3px 0;border-bottom:1px dashed rgba(255,255,255,.08)}
.stats td:first-child{color:var(--muted);padding-right:8px}
#plan{background:#0b0f14;border:1px solid rgba(255,255,255,.08);border-radius:8px;width:360px;height:240px}
.legend{display:flex;gap:10px;flex-wrap:wrap;margin-top:6px}
.chip{display:flex;align-items:center;gap:6px;font-size:12px}
.dot{width:10px;height:10px;border-radius:2px;display:inline-block}
.tip{
position:absolute;z-index:20;pointer-events:none;transform:translate(8px,8px);
background:#111827;border:1px solid rgba(255,255,255,.12);border-radius:8px;padding:8px 10px;font-size:12px;display:none
}
.note{position:absolute;left:12px;bottom:12px;color:var(--muted)}
</style>
</head>
<body>
<div id="app"></div>
<div class="sidebar">
<div class="card">
<h2>控制</h2>
<div class="row">
<label>方案：</label>
<select id="scenario">
<option value="A">方案 A：264 件（全用 520×745×625）</option>
<option value="B" selected>方案 B：282 件（主体 625×745×520 + 尾部 520×745×625）</option>
</select>
</div>
<div class="row">
<label><input type="checkbox" id="onlyLayer"> 只看第</label>
<select id="layerIndex"></select>
<span>层（自地面起）</span>
</div>
<div class="row">
<label><input type="checkbox" id="toggleContainer" checked> 容器</label>
<label><input type="checkbox" id="toggleWire" checked> 线框</label>
<label><input type="checkbox" id="toggleAxes" checked> 坐标轴</label>
<label><input type="checkbox" id="toggleGrid" checked> 网格</label>
</div>
<div class="row"><button id="resetCam">重置视角</button></div>
</div>
<div class="card stats">
<h2>统计</h2>
<table>
<tr><td>容器 (L×W×H)</td><td id="boxDims"></td></tr>
<tr><td>货物 (a×b×c)</td><td id="itemDims"></td></tr>
<tr><td>件数</td><td id="count"></td></tr>
<tr><td>体积利用率</td><td id="util"></td></tr>
<tr><td>选中块</td><td id="selInfo">（悬停查看）</td></tr>
</table>
<div class="legend">
<span class="chip"><span class="dot" style="background:#60a5fa"></span> 主体网格</span>
<span class="chip"><span class="dot" style="background:#f87171"></span> 尾部余长区</span>
<span class="chip"><span class="dot" style="background:#34d399"></span> 可视空区</span>
</div>
</div>
<div class="card">
<h2>分层平面图（顶视，L×W）</h2>
<canvas id="plan" width="360" height="240"></canvas>
<div style="margin-top:6px;color:#9aa4b2">蓝=主体；红=尾部；灰=空区。矩形尺寸即每件货在该层的投影。</div>
</div>
</div>
<div class="tip" id="tooltip"></div>
<div class="note">鼠标左键旋转 · 右键平移 · 滚轮缩放 · 悬停显示坐标</div>
<!-- Import Map（在线CDN） -->
<script type="importmap">
{
"imports": {
"three": "https://unpkg.com/three@0.158.0/build/three.module.js",
"three/addons/": "https://unpkg.com/three@0.158.0/examples/jsm/"
}
}
</script>
<script type="module">
import * as THREE from "three";
import { OrbitControls } from "three/addons/controls/OrbitControls.js";
// ---------- 基础尺寸 ----------
const L=11800,W=2280,H=2600; // 容器
const A_LEN=745,A_WID=625,A_HEI=520; // 单件（固有尺寸）
const SCALE=0.01; // 显示缩放：1 场景单位=10mm
// ---------- three.js 场景 ----------
const scene=new THREE.Scene(); scene.background=new THREE.Color("#0f1216");
const camera=new THREE.PerspectiveCamera(55,innerWidth/innerHeight,0.1,10000);
const renderer=new THREE.WebGLRenderer({antialias:true});renderer.setSize(innerWidth,innerHeight);
document.getElementById("app").appendChild(renderer.domElement);
const controls=new OrbitControls(camera,renderer.domElement);controls.enableDamping=true;controls.dampingFactor=.08;
// 灯、网格、轴
scene.add(new THREE.HemisphereLight(0xffffff,0x222233,.9));
const dir=new THREE.DirectionalLight(0xffffff,.55);dir.position.set(1,2,1);scene.add(dir);
const grid=new THREE.GridHelper(L*SCALE*1.1,22,0x274060,0x243447);scene.add(grid);
const axes=new THREE.AxesHelper(Math.max(L,W,H)*SCALE*.7);scene.add(axes);
// 容器
const containerGroup=new THREE.Group();
const boxGeo=new THREE.BoxGeometry(L*SCALE,H*SCALE,W*SCALE);
const boxMat=new THREE.MeshPhysicalMaterial({color:0x1f2937,transparent:true,opacity:.2,roughness:.9});
const containerMesh=new THREE.Mesh(boxGeo,boxMat);containerMesh.position.set(0,H*SCALE/2,0);containerGroup.add(containerMesh);
const edges=new THREE.LineSegments(new THREE.EdgesGeometry(boxGeo),new THREE.LineBasicMaterial({color:0x8ab4f8}));
edges.position.copy(containerMesh.position);containerGroup.add(edges);
scene.add(containerGroup);
// 原点在容器一个底角（X=长，Y=高，Z=宽）
const originCorner=new THREE.Vector3(-L*SCALE/2,0,-W*SCALE/2);
// ---------- 数据结构（便于分层/平面图/悬停） ----------
let items = []; // {mesh, group:'main'|'tail', size:{x,y,z}, idx:{ix,iy,iz}, pos:{x,y,z}}
const groups = {A:new THREE.Group(), B:new THREE.Group()};
scene.add(groups.A, groups.B);
// 工具函数
function clearGroup(g){ while(g.children.length){ const o=g.children.pop(); if(o.geometry) o.geometry.dispose(); if(o.material) o.material.dispose(); } }
function placeBlock(g, opt){
// opt: {nx,ny,nz,sizeX,sizeY,sizeZ,offsetX,color,tag}
const geo = new THREE.BoxGeometry(opt.sizeX*SCALE,opt.sizeY*SCALE,opt.sizeZ*SCALE);
const mat = new THREE.MeshStandardMaterial({color:opt.color, metalness:.1, roughness:.7});
for(let ix=0;ix<opt.nx;ix++){
for(let iz=0;iz<opt.nz;iz++){
for(let iy=0;iy<opt.ny;iy++){
const mesh=new THREE.Mesh(geo,mat);
const x=opt.offsetX + ix*opt.sizeX;
const y=iy*opt.sizeY;
const z=iz*opt.sizeZ;
mesh.position.set(originCorner.x+(x+opt.sizeX/2)*SCALE,
originCorner.y+(y+opt.sizeY/2)*SCALE,
originCorner.z+(z+opt.sizeZ/2)*SCALE);
mesh.userData = {tag:opt.tag, ix,iy,iz, x,y,z, sx:opt.sizeX, sy:opt.sizeY, sz:opt.sizeZ};
g.add(mesh);
}
}
}
}
function buildScenarioA(){
clearGroup(groups.A);
// 全用 (520×745×625) -> X=520, Z=745, Y=625；22×3×4
placeBlock(groups.A,{nx:22,nz:3,ny:4,sizeX:520,sizeY:625,sizeZ:745,offsetX:0,color:0x60a5fa,tag:'main'});
}
function buildScenarioB(){
clearGroup(groups.B);
// 主体 (625×745×520) -> 18×3×5
placeBlock(groups.B,{nx:18,nz:3,ny:5,sizeX:625,sizeY:520,sizeZ:745,offsetX:0,color:0x60a5fa,tag:'main'});
// 尾部 (520×745×625) -> 1×3×4，offsetX=18*625=11250
placeBlock(groups.B,{nx:1,nz:3,ny:4,sizeX:520,sizeY:625,sizeZ:745,offsetX:18*625,color:0xf87171,tag:'tail'});
}
// 建立两方案
buildScenarioA(); buildScenarioB();
// 剩余空区（用半透明绿色便于理解）
const empties = {A:new THREE.Group(), B:new THREE.Group()};
scene.add(empties.A, empties.B);
function clearAndAddEmpty(g){
clearGroup(g);
const mat = new THREE.MeshStandardMaterial({color:0x34d399,transparent:true,opacity:.25});
// 方案A空区：尾部 360×2280×2600 + 侧边 11440×45×2600 + 顶部 11440×2235×100（演示只画“尾部大空区”）
const a1=new THREE.Mesh(new THREE.BoxGeometry(360*SCALE,2600*SCALE,2280*SCALE),mat);
a1.position.set(originCorner.x+(22*520+360/2)*SCALE, (2600/2)*SCALE, 0);
g.add(a1);
// 方案B空区：尾部余长 30×2280×2600（只示意一块主要空区）
const b1=new THREE.Mesh(new THREE.BoxGeometry(30*SCALE,2600*SCALE,2280*SCALE),mat);
b1.position.set(originCorner.x+(18*625+520+30/2)*SCALE, (2600/2)*SCALE, 0);
empties.B.add(b1);
}
clearAndAddEmpty(empties.A);
// 当前展示
let current = 'B';
groups.A.visible=false; empties.A.visible=false;
groups.B.visible=true; empties.B.visible=true;
// 统计 & 层选择
const el = s=>document.getElementById(s);
function setStats(name,count){
el("boxDims").textContent = `${L}×${W}×${H}`;
el("itemDims").textContent = `${A_LEN}×${A_WID}×${A_HEI}`;
el("count").textContent = `${count} 件（${name}）`;
const util = ((count*A_LEN*A_WID*A_HEI)/(L*W*H)*100).toFixed(2);
el("util").textContent = `${util}%`;
}
function refreshLayerSelect(){
const sel = el("layerIndex");
sel.innerHTML='';
const layers = current==='A' ? 4 : 5; // A:625高 → 4层；B:520高(主体)→5层
for(let i=0;i<layers;i++){
const opt=document.createElement('option'); opt.value=i; opt.textContent=i; sel.appendChild(opt);
}
}
// 只看某层
function applyLayerFilter(){
const only = el("onlyLayer").checked;
const idx = parseInt(el("layerIndex").value,10);
const g = current==='A' ? groups.A : groups.B;
g.traverse(o=>{
if(!o.isMesh) return;
const iy = o.userData?.iy ?? 0;
o.visible = only ? (iy===idx) : true;
});
// 空区在分层模式下仍显示（帮助理解），你也可以隐藏：
// (el("onlyLayer").checked) ? empties[current].visible=false : empties[current].visible=true;
drawPlan(); // 更新平面图
}
// 平面图：按层绘制矩形
const plan = el("plan"); const ctx=plan.getContext('2d');
function drawRect(x,y,w,h,color){
ctx.fillStyle=color; ctx.fillRect(x,y,w,h);
ctx.strokeStyle='#1f2937'; ctx.lineWidth=1; ctx.strokeRect(x,y,w,h);
}
function drawPlan(){
const PAD=8, WW=plan.width-2*PAD, HH=plan.height-2*PAD;
ctx.clearRect(0,0,plan.width,plan.height);
// 尺度：X=长(L)，Y=宽(W)
const sx = WW / L, sz = HH / W;
// 画容器边界
ctx.strokeStyle='#8ab4f8'; ctx.lineWidth=1.2;
ctx.strokeRect(PAD, PAD, L*sx, W*sz);
// 画货物（选中层 or 全部）
const only = el("onlyLayer").checked;
const target = current==='A' ? groups.A : groups.B;
target.children.forEach(mesh=>{
if(!mesh.isMesh) return;
const u=mesh.userData;
const show = !only || (u.iy===parseInt(el("layerIndex").value,10));
if(!show) return;
// 顶视投影尺寸：长×宽 = sizeX × sizeZ
const x = PAD + u.x*sx;
const y = PAD + u.z*sz;
const w = u.sx*sx;
const h = u.sz*sz;
const color = u.tag==='main' ? '#60a5fa' : '#f87171';
drawRect(x,y,w,h,color);
});
// 主要空区示意
ctx.globalAlpha=0.25; ctx.fillStyle='#34d399';
if(current==='A'){ // 尾部 360×2280
ctx.fillRect(PAD + (22*520)*sx, PAD, 360*sx, W*sz);
} else { // B 尾部 30×2280
ctx.fillRect(PAD + (18*625+520)*sx, PAD, 30*sx, W*sz);
}
ctx.globalAlpha=1;
}
// 悬停提示：显示 (ix,iy,iz) 与 (x,y,z)
const tooltip = el('tooltip');
const raycaster=new THREE.Raycaster(); const mouse=new THREE.Vector2();
function onPointerMove(ev){
const rect=renderer.domElement.getBoundingClientRect();
mouse.x = ((ev.clientX-rect.left)/rect.width)*2 - 1;
mouse.y = -((ev.clientY-rect.top)/rect.height)*2 + 1;
raycaster.setFromCamera(mouse,camera);
const g = current==='A' ? groups.A : groups.B;
const hits = raycaster.intersectObjects(g.children,false);
if(hits.length){
const m = hits[0].object; const u=m.userData;
tooltip.style.display='block';
tooltip.style.left=ev.clientX+'px'; tooltip.style.top=ev.clientY+'px';
tooltip.innerHTML = `
<div><b>${u.tag==='main'?'主体':'尾部'}</b> · 货物</div>
<div>网格索引 ix=${u.ix}, iy=${u.iy}, iz=${u.iz}</div>
<div>原点坐标 (mm)：x=${u.x}, y=${u.y}, z=${u.z}</div>
<div>朝向尺寸 (L×W×H)：${u.sx}×${u.sz}×${u.sy}</div>
`;
el("selInfo").textContent = `ix=${u.ix}, iy=${u.iy}, iz=${u.iz}（x=${u.x}, y=${u.y}, z=${u.z} mm）`;
}else{
tooltip.style.display='none';
el("selInfo").textContent = '（悬停查看）';
}
}
renderer.domElement.addEventListener('pointermove', onPointerMove);
// 相机 & 初始状态
function resetCam(){
const diag=Math.sqrt(L*L+W*W+H*H)*SCALE;
camera.position.set(diag*.9,H*SCALE*.9,diag*.9);
controls.target.set(0,H*SCALE/2,0);
controls.update();
}
resetCam();
// UI
function setScenario(v){
current = v;
groups.A.visible = (v==='A');
empties.A.visible = (v==='A');
groups.B.visible = (v==='B');
empties.B.visible = (v==='B');
setStats(v==='A'?'方案 A':'方案 B', v==='A'?264:282);
refreshLayerSelect();
applyLayerFilter();
}
document.getElementById('scenario').addEventListener('change', e=> setScenario(e.target.value));
document.getElementById('onlyLayer').addEventListener('change', applyLayerFilter);
document.getElementById('layerIndex').addEventListener('change', applyLayerFilter);
document.getElementById('toggleContainer').addEventListener('change', e=> containerGroup.visible=e.target.checked);
document.getElementById('toggleWire').addEventListener('change', e=> edges.visible=e.target.checked);
document.getElementById('toggleAxes').addEventListener('change', e=> axes.visible=e.target.checked);
document.getElementById('toggleGrid').addEventListener('change', e=> grid.visible=e.target.checked);
document.getElementById('resetCam').addEventListener('click', resetCam);
// 初始：方案B
setScenario('B');
// 渲染循环
function animate(){ requestAnimationFrame(animate); controls.update(); renderer.render(scene,camera); }
animate();
// 画一次平面图
drawPlan();
// 自适应
onresize=()=>{ camera.aspect=innerWidth/innerHeight; camera.updateProjectionMatrix(); renderer.setSize(innerWidth,innerHeight); drawPlan(); }
</script>
</body>
</html>
然后经过一系列的讨论最后得到
单一朝向最优 + 条带混合最优
import java.util.*;
import java.util.stream.Collectors;
/**
* 3D 装箱（刚性长方体、正交摆放）：
* - 方案1：单一朝向整齐网格（6种朝向枚举）
* - 方案2：条带混合：沿宽W分条带（条带宽度取自 {a,b,c}），每条带内沿长L用两种可选列宽做无界背包，条带之间再对宽W做无界背包
* 结果返回两者较优者（件数最大；若并列，剩余体积更小者）。
*
* 备注：
* - 时间复杂度主要取决于 L/gLen 与 W/gWid（g为相应gcd）。以毫米建模，g通常是5/10等小数，几千状态量级，毫秒级可跑。
* - 仅支持单一SKU（同尺寸），但代码结构易于扩展。
*/
public class Packing3DOptimizer {
/** 切换是否打印坐标（可能很多行），默认false */
static final boolean PRINT_COORDS = false;
/** 示例：容器与货物尺寸（毫米） */
static final int L = 11800, W = 2280, H = 2600;
// 把下面改成 {745,625,520} 可验证 282；当前 {765,625,520} 会得到 264
static final int[] ITEM = new int[]{765, 625, 520};
public static void main(String[] args) {
Result best = solveBest(L, W, H, ITEM[0], ITEM[1], ITEM[2]);
System.out.println(best.summary());
if (PRINT_COORDS) {
System.out.println("\n# Placements (x,y,z, len,hei,wid):");
best.printPlacements();
}
}
/** 求两类方案的较优者 */
public static Result solveBest(int L, int W, int H, int a, int b, int c) {
Result single = solveSingleOrientation(L, W, H, a, b, c);
Result stripMix = solveStripMix(L, W, H, a, b, c);
if (stripMix == null || single.packedCount > stripMix.packedCount) {
return single;
} else if (stripMix.packedCount > single.packedCount) {
return stripMix;
} else {
// 件数相同 → 选剩余体积更小的
long volBox = 1L * L * W * H;
long volItem = 1L * a * b * c;
long rem1 = volBox - volItem * single.packedCount;
long rem2 = volBox - volItem * stripMix.packedCount;
return (rem1 <= rem2) ? single : stripMix;
}
}
/** 方案1：单一朝向整齐网格（6种朝向枚举） */
public static Result solveSingleOrientation(int L, int W, int H, int a, int b, int c) {
List<int[]> perms = permutations(a, b, c); // 每个是 [x(length), y(height), z(width)]
int best = -1; int[] bestOri = null;
int bx=0, by=0, bz=0;
for (int[] ori : perms) {
int nx = L / ori[0];
int ny = H / ori[1];
int nz = W / ori[2];
int cnt = nx * ny * nz;
if (cnt > best) { best = cnt; bestOri = ori; bx = nx; by = ny; bz = nz; }
}
Result r = new Result(Result.Type.SINGLE);
r.packedCount = best;
r.singleOri = bestOri; // x,y,z
r.singleNx = bx; r.singleNy = by; r.singleNz = bz;
r.L=L; r.W=W; r.H=H; r.item = new int[]{a,b,c};
return r;
}
/** 方案2：条带混合（两层无界背包） */
public static Result solveStripMix(int L, int W, int H, int a, int b, int c) {
// 候选条带宽度：来自 {a,b,c} 去重
int[] widths = Arrays.stream(new int[]{a,b,c}).distinct().toArray();
List<BandCandidate> bandCands = new ArrayList<>();
for (int w : widths) {
// 该条带宽= w 时，条带内可用的两种列（对应两个朝向）：
int[] others = others(a,b,c,w); // 另外两边
// 列1：x=others[0], y=others[1], z=w
// 列2：x=others[1], y=others[0], z=w
List<Col> cols = new ArrayList<>(2);
int q1 = H / others[1];
if (q1 > 0) cols.add(new Col(others[0], others[1], w, q1));
int q2 = H / others[0];
if (q2 > 0) cols.add(new Col(others[1], others[0], w, q2));
if (cols.isEmpty()) continue;
LenDP lenDP = solveLenUnboundedKnapsack(L, cols);
if (lenDP.bestValue <= 0) continue;
bandCands.add(new BandCandidate(w, lenDP));
}
if (bandCands.isEmpty()) return null;
// 宽度向无界背包：物品=条带；重量=条带宽；价值=该条带长度DP的最优件数
int gW = gcd(bandCands.stream().map(b -> b.width).collect(Collectors.toList()));
int cap = W / gW;
int n = bandCands.size();
int[] dp = new int[cap+1];
int[] prev = new int[cap+1];
int[] pick = new int[cap+1];
Arrays.fill(prev, -1);
Arrays.fill(pick, -1);
for (int cpos = 0; cpos <= cap; cpos++) {
for (int i = 0; i < n; i++) {
int wUnits = bandCands.get(i).width / gW;
int v = bandCands.get(i).len.bestValue;
int next = cpos + wUnits;
if (next <= cap && dp[cpos] + v > dp[next]) {
dp[next] = dp[cpos] + v;
prev[next] = cpos;
pick[next] = i;
}
}
}
// 取任意宽度≤W的最优
int bestIdx = 0;
for (int i = 1; i <= cap; i++) if (dp[i] > dp[bestIdx]) bestIdx = i;
// 回溯条带选择
Map<Integer,Integer> bandCount = new LinkedHashMap<>(); // key = width mm, value = strips
List<BandUse> bandUses = new ArrayList<>();
int cur = bestIdx;
while (cur > 0 && pick[cur] != -1) {
int bi = pick[cur];
BandCandidate b = bandCands.get(bi);
bandCount.merge(b.width, 1, Integer::sum);
bandUses.add(new BandUse(b.width, b.len)); // 记录一次条带（每次都用同一个条带长度DP方案）
cur = prev[cur];
}
Collections.reverse(bandUses);
Result r = new Result(Result.Type.STRIP_MIX);
r.packedCount = dp[bestIdx];
r.bandUses = bandUses;
r.L=L; r.W=W; r.H=H; r.item = new int[]{a,b,c};
return r;
}
/** 单条带内的长度无界背包：物品=列（列长=x；价值=该列的层数q），容量=L；返回最优件数与列组合 */
static LenDP solveLenUnboundedKnapsack(int L, List<Col> cols) {
// 去除无效列（q<=0 或 x>L）
List<Col> list = new ArrayList<>();
for (Col c : cols) if (c.x > 0 && c.q > 0 && c.x <= L) list.add(c);
if (list.isEmpty()) return new LenDP(0, 0, new int[0], list, 1);
int g = gcd(list.stream().map(c -> c.x).collect(Collectors.toList()));
int cap = L / g;
int m = list.size();
int[] weight = new int[m], val = new int[m];
for (int i = 0; i < m; i++) { weight[i] = list.get(i).x / g; val[i] = list.get(i).q; }
int[] dp = new int[cap+1];
int[] prev = new int[cap+1];
int[] pick = new int[cap+1];
Arrays.fill(prev, -1); Arrays.fill(pick, -1);
for (int cpos = 0; cpos <= cap; cpos++) {
for (int i = 0; i < m; i++) {
int next = cpos + weight[i];
if (next <= cap && dp[cpos] + val[i] > dp[next]) {
dp[next] = dp[cpos] + val[i];
prev[next] = cpos;
pick[next] = i;
}
}
}
// 允许长度有余 → 取≤L 的最优
int bestIdx = 0;
for (int i = 1; i <= cap; i++) if (dp[i] > dp[bestIdx]) bestIdx = i;
// 回溯列选择，统计每种列的数量
int[] counts = new int[m];
int cur = bestIdx;
while (cur > 0 && pick[cur] != -1) {
int i = pick[cur];
counts[i]++;
cur = prev[cur];
}
int usedUnits = bestIdx; // used length in units of g
return new LenDP(dp[bestIdx], usedUnits * g, counts, list, g);
}
// ========== 工具 & 数据结构 ==========
static int gcd(int a, int b) { a = Math.abs(a); b = Math.abs(b); if (a==0) return b; if (b==0) return a;
while (b != 0) { int t = a % b; a = b; b = t; } return a; }
static int gcd(Collection<Integer> vals) {
int g = 0; for (int v : vals) g = gcd(g, v); return g == 0 ? 1 : g;
}
static List<int[]> permutations(int a, int b, int c) {
List<int[]> p = new ArrayList<>(6);
p.add(new int[]{a,b,c}); p.add(new int[]{a,c,b});
p.add(new int[]{b,a,c}); p.add(new int[]{b,c,a});
p.add(new int[]{c,a,b}); p.add(new int[]{c,b,a});
return p;
}
static int[] others(int a, int b, int c, int chosenAsZ) {
if (a==chosenAsZ) return new int[]{b,c};
if (b==chosenAsZ) return new int[]{a,c};
return new int[]{a,b};
}
/** 一列（固定条带宽z时的一个朝向）：占用长度x，高度y，条带宽z；该列可叠 q 层 */
static class Col {
final int x, y, z, q;
Col(int x, int y, int z, int q) { this.x=x; this.y=y; this.z=z; this.q=q; }
}
/** 单条带长度DP结果 */
static class LenDP {
final int bestValue; // 该条带内最大件数
final int usedLen; // 实际使用的长度（≤L）
final int[] counts; // 每种列（Col）的数量
final List<Col> cols; // 列类型（与counts对齐）
final int g; // 长度DP的gcd
LenDP(int bestValue, int usedLen, int[] counts, List<Col> cols, int g){
this.bestValue = bestValue; this.usedLen = usedLen; this.counts = counts; this.cols = cols; this.g = g;
}
}
/** 条带候选：宽度+该条带在长度DP的最优 */
static class BandCandidate {
final int width;
final LenDP len;
BandCandidate(int width, LenDP len){ this.width=width; this.len=len; }
}
/** 回溯用：一次条带的具体使用（复用候选中的len方案） */
static class BandUse {
final int width;
final LenDP len;
BandUse(int width, LenDP len){ this.width=width; this.len=len; }
}
/** 最终方案 */
static class Result {
enum Type { SINGLE, STRIP_MIX }
final Type type;
int packedCount;
// 通用信息
int L,W,H; int[] item;
// 单一朝向
int[] singleOri; // x,y,z
int singleNx, singleNy, singleNz;
// 条带混合
List<BandUse> bandUses;
Result(Type t){ this.type = t; }
String summary(){
StringBuilder sb = new StringBuilder();
sb.append("容器: ").append(L).append("×").append(W).append("×").append(H)
.append("；货物: ").append(item[0]).append("×").append(item[1]).append("×").append(item[2]).append("\n");
sb.append("最优方案：").append(type==Type.SINGLE ? "单一朝向整齐网格" : "条带混合").append("\n");
sb.append("最大件数：").append(packedCount).append("\n");
if (type == Type.SINGLE) {
sb.append("朝向(长×高×宽) = ").append(singleOri[0]).append("×").append(singleOri[1]).append("×").append(singleOri[2]).append("\n");
sb.append("沿长×沿宽×沿高 = ").append(singleNx).append(" × ").append(singleNz).append(" × ").append(singleNy).append("\n");
} else {
// 汇总条带统计
Map<Integer, Integer> counter = new LinkedHashMap<>();
for (BandUse u : bandUses) counter.merge(u.width, 1, Integer::sum);
sb.append("条带列表（宽 mm → 条带数）：").append(counter).append("\n");
sb.append("各条带内的列组合（按宽分组）：\n");
int idx=1;
for (BandUse u : bandUses) {
sb.append(" - 条带#").append(idx++).append(" 宽=").append(u.width)
.append("：长度用量≈").append(u.len.usedLen).append("/")
.append(L).append("；件数=").append(u.len.bestValue).append("\n");
for (int i = 0; i < u.len.cols.size(); i++){
Col c = u.len.cols.get(i);
int cnt = u.len.counts[i];
if (cnt>0) {
sb.append(" 列：长=").append(c.x).append(" 高=").append(c.y)
.append("（层数=").append(c.q).append("） × ").append(cnt).append(" 列\n");
}
}
}
}
// 利用率
long volBox = 1L * L * W * H;
long volItem = 1L * item[0] * item[1] * item[2];
double util = (packedCount * (double)volItem) / volBox * 100.0;
sb.append(String.format("体积利用率：%.2f%%\n", util));
return sb.toString();
}
/** 打印坐标（很多行）：(x,y,z,len,hei,wid)。单一朝向是整齐网格；条带混合按条带宽→列→层生成。 */
void printPlacements() {
if (type == Type.SINGLE) {
int x=singleOri[0], y=singleOri[1], z=singleOri[2];
for (int ix=0; ix<singleNx; ix++){
for (int iz=0; iz<singleNz; iz++){
for (int iy=0; iy<singleNy; iy++){
int X = ix * x;
int Y = iy * y;
int Z = iz * z;
System.out.printf("%d,%d,%d,%d,%d,%d%n", X,Y,Z, x,y,z);
}
}
}
} else {
// 条带混合
int zOffset = 0;
for (BandUse b : bandUses) {
int xOffset = 0;
// 每个条带用同一套列组合（回溯出来的）
List<Col> cols = b.len.cols;
int[] cnts = b.len.counts.clone();
// 简单策略：按“列长大到小”排布更规整
Integer[] ord = new Integer[cols.size()];
for (int i=0;i<cols.size();i++) ord[i]=i;
Arrays.sort(ord, (i,j)->Integer.compare(cols.get(j).x, cols.get(i).x));
for (int idx=0; idx<ord.length; idx++){
int i = ord[idx];
Col c = cols.get(i);
for (int k=0; k<cnts[i]; k++){
// 在该列上竖向叠 q 层
for (int h=0; h<c.q; h++){
int X = xOffset;
int Y = h * c.y;
int Z = zOffset;
System.out.printf("%d,%d,%d,%d,%d,%d%n", X,Y,Z, c.x,c.y,c.z);
}
xOffset += c.x;
}
}
zOffset += b.width;
}
}
}
}
}
一句话总结：通过比较"单一朝向整齐排列"和"条带混合布局"两种策略，选择装箱件数更多的方案，核心创新是将容器分条带后用两层无界背包DP实现高效优化
后续：支持多SKU