固定箱数装箱问题的NP-hardness判定咨询

背景与参考依据 #

• 一般装箱问题属于NP完全问题。
• 维基百科相关结论：

  计算层面上该问题是NP-hard，对应的判定问题——判断物品能否装入指定数量的箱子——是NP-complete；另一方面，对于任意固定箱数K，装箱问题可在伪多项式时间内求解；对于任意固定箱容量B，可在多项式时间内求解。

• 论文《Bin packing with fixed number of bins revisited》指出：若物品尺寸为多项式有界整数，固定箱数的装箱问题可在n^(O(k))时间内求解。

具体疑问 #

给定固定数量m、固定容量的箱子，分两种场景：

• 离线场景：所有物品集提前已知
• 在线场景：物品按顺序到达，后续物品未知
  基于现有资料，假设该问题并非NP-hard（理由是可通过穷举搜索求解），求证该结论是否成立。

结论 #

1. 离线场景：假设成立，该问题不属于NP-hard。
   • 当箱数m固定时，即便采用穷举思路，结合箱容量约束，实际可通过动态规划等方法优化到伪多项式时间复杂度；若物品尺寸为多项式有界整数，甚至能达到n^(O(m))的多项式时间复杂度（符合论文结论）。根据NP-hard的定义，这类可在多项式/伪多项式时间内求解的问题，显然不属于NP-hard范畴（除非P=NP的极端情况成立）。
2. 在线场景：无法用NP-hard的概念直接判定，且不存在最优多项式时间算法。
   • 在线场景下无法提前获取全部物品信息，穷举搜索完全不可行，只能依赖近似算法（如首次适应、最佳适应策略），但这类算法无法保证得到最优解。在线问题的复杂度评估框架和离线NP问题体系不同，不能直接套用NP-hard的归类逻辑。

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