如何获取Best Fit装箱算法的箱数与各箱物品，及算法优化方法？

核心需求：获取总箱数及每个箱子的物品详情 #

实现思路 #

• 先定义一个箱子类，用来记录箱子的剩余容量和内部物品列表：

  public class Bin
  {
      public int RemainingCapacity { get; set; }
      public List<int> Items { get; set; } = new List<int>();
  }
  

• 把原算法中仅跟踪剩余容量的结构，替换成List<Bin>集合来管理所有箱子：
  • 遍历每个物品时，逐个检查已有的箱子，找到剩余容量能装下当前物品且剩余容量最小的箱子（这是Best Fit的核心逻辑）
  • 找到符合条件的箱子后，把物品加入该箱子的物品列表，同时更新剩余容量
  • 没有找到适配箱子时，新建一个箱子放入当前物品，再添加到箱子集合里
• 最终总箱数就是箱子集合的Count值，遍历集合就能拿到每个箱子的物品明细

代码示例片段 #

// 初始化箱子集合
List<Bin> bins = new List<Bin>();
int binCapacity = 10; // 示例箱子容量
int[] items = { 4, 8, 1, 4, 2, 1 };

foreach (int item in items)
{
    int bestBinIndex = -1;
    int minLeftSpace = binCapacity + 1;

    // 寻找最佳适配箱子
    for (int i = 0; i < bins.Count; i++)
    {
        if (bins[i].RemainingCapacity >= item && bins[i].RemainingCapacity - item < minLeftSpace)
        {
            minLeftSpace = bins[i].RemainingCapacity - item;
            bestBinIndex = i;
        }
    }

    if (bestBinIndex != -1)
    {
        // 放入已有箱子
        bins[bestBinIndex].Items.Add(item);
        bins[bestBinIndex].RemainingCapacity -= item;
    }
    else
    {
        // 创建新箱子
        Bin newBin = new Bin { RemainingCapacity = binCapacity - item };
        newBin.Items.Add(item);
        bins.Add(newBin);
    }
}

// 输出结果
Console.WriteLine($"总箱数: {bins.Count}");
for (int i = 0; i < bins.Count; i++)
{
    Console.WriteLine($"箱子{i+1}的物品: {string.Join(", ", bins[i].Items)}，剩余容量: {bins[i].RemainingCapacity}");
}

可选需求：Best Fit算法的优化方案 #

Best Fit属于启发式算法，本身不遍历所有组合（否则就是NP难的精确解法），可以从这些方向优化：

• 排序预处理：先把物品按从大到小排序，再执行Best Fit（即Best Fit Decreasing算法），大物品优先放置能避免小物品占用空间导致大物品无法放入的情况，大幅减少总箱数
• 数据结构优化：用优先队列（最小堆）存储箱子的剩余容量，快速找到剩余容量最小且能容纳当前物品的箱子，把查找最佳箱子的时间复杂度从O(n)降到O(log n)
• 场景化调整：针对物品大小集中在特定区间的场景，划分不同容量的箱子类型；或者增加"重新整理"步骤，将多个箱子的物品重新分配合并出空箱子（会增加算法复杂度）
• 规则简化：设定阈值，当箱子剩余容量小于某个值时直接放入新箱子，减少无效查找；或者对相似大小的物品进行批量处理

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