给定2D物品尺寸价值与n×n容器，求解可装入物品的最大价值

这个问题属于带空间布局约束的二维无界背包问题，和普通单重量约束的背包、只要求装下的装箱问题都有区别，核心约束为：容器为n×n正方形、物品为可旋转矩形、同物品可重复使用、目标是总价值最大。

问题示例（你提供的输入） #

容器尺寸：10 x 10
物品列表：
[
    {w: 3, h: 5, value: 160},
    {w: 5, h: 5, value: 250},
    {w: 2, h: 5, value: 150},
    {w: 2, h: 3, value: 10}
]
约束：
- 物品为任意矩形，允许旋转90度
- 同物品可无限制重复使用
- n ≤ 20

为什么贪心算法失效 #

和普通无界背包的贪心局限性一致：优先放单位面积价值最高的物品，往往会留下大量无法利用的零碎空间，总价值反而不如牺牲少量单位价值、填满更多空间的组合，无法保证全局最优。

正确求解方案（n≤20场景下可求精确最优解） #

因为n最大只有20，容器总格子数仅400，用动态规划+矩形分治切割的方法可以在极低耗时下得到精确最优解，步骤如下：

步骤1：预处理物品池 #

• 把所有可旋转的物品的旋转后尺寸加入物品池：比如w=3、h=5的物品，旋转后得到w=5、h=3的新物品，如果和原尺寸不一致就加入，避免后续重复判断旋转逻辑
• 过滤冗余物品：如果物品A的宽、高都小于等于物品B，且价值大于等于B，直接删除物品B，它永远不可能出现在最优解里

步骤2：动态规划状态定义 #

定义dp[w][h]为宽为w、高为h的矩形空间能获得的最大价值，我们从小到大遍历所有宽和高（从1到n），最终dp[n][n]就是所求的最大价值。

步骤3：状态转移逻辑 #

对于每个dp[w][h]，取以下三种情况的最大值：

1. 不放任何物品，基础价值为0
2. 遍历所有物品，若物品i的宽wi ≤ w且高hi ≤ h，则放入物品i后，剩余的L型空间有两种合法切割方式，避免重复计算：
   • 横向切：剩余空间拆为宽wi × 高(h-hi)和宽(w-wi) × 高h两个矩形，总价值为 value_i + dp[wi][h-hi] + dp[w-wi][h]
   • 纵向切：剩余空间拆为宽(w-wi) × 高hi和宽w × 高(h-hi)两个矩形，总价值为 value_i + dp[w-wi][hi] + dp[w][h-hi]
3. 不放置单个新物品，直接把当前矩形切为两个更小的矩形，取最大值：
   • 沿宽度切：max(dp[k][h] + dp[w-k][h])，k从1到w-1
   • 沿高度切：max(dp[w][k] + dp[w][h-k])，k从1到h-1

步骤4：可选（输出具体摆放方案） #

如果需要输出每个物品的摆放位置，只需要在DP转移时额外记录每个dp[w][h]的最优转移来源，最后回溯即可还原所有物品的摆放坐标和尺寸。

补充说明 #

如果n超过30，精确DP的复杂度会快速上升，此时可以用模拟退火、遗传算法等启发式方法求近似最优解，对于n≤20的场景，上述精确DP方案完全可以满足需求。

内容的提问来源于stack exchange，提问作者Helen Gillson