当前位置： 首页 > article >正文

贪心算法应用：装箱问题(BFD算法)详解

article 2025/8/26 8:55:07

在这里插入图片描述

贪心算法应用：装箱问题(BFD算法)详解

1. 装箱问题与BFD算法概述

1.1 装箱问题定义

装箱问题(Bin Packing Problem)是组合优化中的经典问题，其定义为：

  • 给定n个物品，每个物品有大小wᵢ (0 < wᵢ ≤ C)
  • 无限数量的箱子，每个箱子容量为C
  • 目标：用最少数量的箱子装下所有物品

1.2 BFD算法简介

最佳适应递减算法(Best Fit Decreasing, BFD)是解决装箱问题的高效启发式算法：

  1. 先将所有物品按大小降序排序
  2. 然后对每个物品，将其放入能容纳它且剩余空间最小的箱子
  3. 若无合适箱子，则开启新箱子

与FFD的区别：

  • FFD选择第一个能装下物品的箱子
  • BFD选择最适合(剩余空间最小)的箱子

2. BFD算法详细解析

2.1 算法思想

BFD算法的核心思想是：

  • 排序阶段：大物品优先处理，减少碎片空间
  • 放置阶段：每次选择最合适的箱子，提高空间利用率

2.2 算法步骤

  1. 输入：物品列表items，箱子容量C
  2. 排序：将items按非递增顺序排序
  3. 初始化：创建空箱子列表bins
  4. 分配物品：
    • 对于每个物品item：
      • 遍历所有箱子，找到满足条件且剩余空间最小的箱子
      • 若找到，放入该箱子
      • 若未找到，创建新箱子并放入
  5. 输出：使用的箱子列表

2.3 伪代码表示

function BFD(items, C):sortedItems = sortDescending(items)bins = []for item in sortedItems:bestBin = nullminSpace = C + 1  // 初始化为大于最大可能值for bin in bins:space = C - bin.currentWeightif space >= item and space < minSpace:bestBin = binminSpace = spaceif bestBin != null:bestBin.add(item)else:newBin = new Bin(C)newBin.add(item)bins.add(newBin)return bins

3. Java实现BFD算法

3.1 基础实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class BinPackingBFD {public static void main(String[] args) {List<Integer> items = List.of(4, 8, 5, 1, 2, 3, 6, 7, 9, 4);int binCapacity = 10;List<List<Integer>> bins = bestFitDecreasing(items, binCapacity);printBins(bins);}public static List<List<Integer>> bestFitDecreasing(List<Integer> items, int binCapacity) {// 复制并排序物品列表List<Integer> sortedItems = new ArrayList<>(items);Collections.sort(sortedItems, Collections.reverseOrder());List<List<Integer>> bins = new ArrayList<>();List<Integer> binCapacities = new ArrayList<>(); // 跟踪每个箱子的已用容量for (int item : sortedItems) {// 寻找最佳箱子int bestBinIndex = -1;int minRemaining = binCapacity + 1; // 初始化为不可能的值for (int i = 0; i < bins.size(); i++) {int remaining = binCapacity - binCapacities.get(i);if (remaining >= item && remaining < minRemaining) {bestBinIndex = i;minRemaining = remaining;}}// 放置物品if (bestBinIndex != -1) {bins.get(bestBinIndex).add(item);binCapacities.set(bestBinIndex, binCapacities.get(bestBinIndex) + item);} else {List<Integer> newBin = new ArrayList<>();newBin.add(item);bins.add(newBin);binCapacities.add(item);}}return bins;}private static void printBins(List<List<Integer>> bins) {System.out.println("使用的箱子数量: " + bins.size());for (int i = 0; i < bins.size(); i++) {List<Integer> bin = bins.get(i);int sum = bin.stream().mapToInt(Integer::intValue).sum();System.out.printf("箱子 %d: %s (总大小: %d)%n", i+1, bin, sum);}}
}

3.2 面向对象优化实现

import java.util.*;public class BinPackingBFDAdvanced {public static void main(String[] args) {List<Integer> items = List.of(4, 8, 5, 1, 2, 3, 6, 7, 9, 4);int binCapacity = 10;BinPackingResult result = packItemsBFD(items, binCapacity);result.printBins();}static class Bin {private final int capacity;private final List<Integer> items;private int currentWeight;public Bin(int capacity) {this.capacity = capacity;this.items = new ArrayList<>();this.currentWeight = 0;}public boolean canAdd(int item) {return currentWeight + item <= capacity;}public void addItem(int item) {if (!canAdd(item)) {throw new IllegalStateException("超出箱子容量");}items.add(item);currentWeight += item;}public int getRemainingCapacity() {return capacity - currentWeight;}public List<Integer> getItems() {return Collections.unmodifiableList(items);}public int getCurrentWeight() {return currentWeight;}}static class BinPackingResult {private final List<Bin> bins;private final int binCapacity;public BinPackingResult(List<Bin> bins, int binCapacity) {this.bins = bins;this.binCapacity = binCapacity;}public void printBins() {System.out.println("使用的箱子数量: " + bins.size());System.out.printf("平均填充率: %.2f%%%n", getAverageFillRate() * 100);for (int i = 0; i < bins.size(); i++) {Bin bin = bins.get(i);System.out.printf("箱子 %2d: %s (总大小: %2d, 填充率: %5.2f%%)%n",i+1, bin.getItems(), bin.getCurrentWeight(),(double)bin.getCurrentWeight() / binCapacity * 100);}}public double getAverageFillRate() {return bins.stream().mapToDouble(bin -> (double)bin.getCurrentWeight() / binCapacity).average().orElse(0);}}public static BinPackingResult packItemsBFD(List<Integer> items, int binCapacity) {// 验证输入validateInput(items, binCapacity);// 排序物品List<Integer> sortedItems = new ArrayList<>(items);sortedItems.sort(Collections.reverseOrder());List<Bin> bins = new ArrayList<>();for (int item : sortedItems) {Bin bestBin = findBestBin(bins, item, binCapacity);if (bestBin != null) {bestBin.addItem(item);} else {Bin newBin = new Bin(binCapacity);newBin.addItem(item);bins.add(newBin);}}return new BinPackingResult(bins, binCapacity);}private static Bin findBestBin(List<Bin> bins, int item, int binCapacity) {Bin bestBin = null;int minRemaining = binCapacity + 1;for (Bin bin : bins) {if (bin.canAdd(item)) {int remaining = bin.getRemainingCapacity() - item;if (remaining < minRemaining) {bestBin = bin;minRemaining = remaining;}}}return bestBin;}private static void validateInput(List<Integer> items, int binCapacity) {if (binCapacity <= 0) {throw new IllegalArgumentException("箱子容量必须为正数");}for (int item : items) {if (item <= 0) {throw new IllegalArgumentException("物品大小必须为正数");}if (item > binCapacity) {throw new IllegalArgumentException("存在物品大小超过箱子容量");}}}
}

3.3 使用TreeSet优化查找

import java.util.*;public class BinPackingBFDWithTreeSet {public static void main(String[] args) {List<Integer> items = List.of(4, 8, 5, 1, 2, 3, 6, 7, 9, 4);int binCapacity = 10;BinPackingResult result = packItemsBFD(items, binCapacity);result.printBins();}static class Bin implements Comparable<Bin> {private final int capacity;private final List<Integer> items;private int currentWeight;public Bin(int capacity) {this.capacity = capacity;this.items = new ArrayList<>();this.currentWeight = 0;}public boolean canAdd(int item) {return currentWeight + item <= capacity;}public void addItem(int item) {if (!canAdd(item)) {throw new IllegalStateException("超出箱子容量");}items.add(item);currentWeight += item;}public int getRemainingCapacity() {return capacity - currentWeight;}public List<Integer> getItems() {return Collections.unmodifiableList(items);}@Overridepublic int compareTo(Bin other) {// 按剩余容量升序排列return Integer.compare(this.getRemainingCapacity(), other.getRemainingCapacity());}}static class BinPackingResult {private final List<Bin> bins;public BinPackingResult(List<Bin> bins) {this.bins = bins;}public void printBins() {System.out.println("使用的箱子数量: " + bins.size());for (int i = 0; i < bins.size(); i++) {Bin bin = bins.get(i);System.out.printf("箱子 %2d: %s (总大小: %2d)%n",i+1, bin.getItems(), bin.currentWeight);}}}public static BinPackingResult packItemsBFD(List<Integer> items, int binCapacity) {// 排序物品List<Integer> sortedItems = new ArrayList<>(items);sortedItems.sort(Collections.reverseOrder());List<Bin> bins = new ArrayList<>();TreeSet<Bin> binTree = new TreeSet<>();for (int item : sortedItems) {// 创建一个临时bin用于查找Bin tempBin = new Bin(binCapacity);tempBin.addItem(binCapacity - item); // 剩余容量=item的箱子// 找到剩余容量 >= item的最小箱子Bin candidate = binTree.ceiling(tempBin);if (candidate != null && candidate.canAdd(item)) {// 从TreeSet中移除，修改后再添加回去binTree.remove(candidate);candidate.addItem(item);binTree.add(candidate);} else {Bin newBin = new Bin(binCapacity);newBin.addItem(item);bins.add(newBin);binTree.add(newBin);}}return new BinPackingResult(bins);}
}

4. 算法分析与性能优化

4.1 时间复杂度分析

  1. 排序阶段：O(n log n)
  2. 装箱阶段：
    • 基础实现：O(n²) - 每个物品遍历所有箱子
    • TreeSet优化：O(n log n) - 每次查找O(log n)

4.2 空间复杂度

  • O(n) - 需要存储所有物品和箱子信息

4.3 性能对比测试

import java.util.*;
import java.util.stream.IntStream;public class BFDPerformanceTest {public static void main(String[] args) {int numItems = 100000;int binCapacity = 100;List<Integer> items = generateRandomItems(numItems, binCapacity);// 预热BinPackingBFD.bestFitDecreasing(items.subList(0, 1000), binCapacity);BinPackingBFDAdvanced.packItemsBFD(items.subList(0, 1000), binCapacity);// 测试基础实现long start = System.currentTimeMillis();List<List<Integer>> bins1 = BinPackingBFD.bestFitDecreasing(items, binCapacity);long end = System.currentTimeMillis();System.out.printf("基础BFD实现: %5dms, 箱子数: %d%n", end-start, bins1.size());// 测试高级实现start = System.currentTimeMillis();BinPackingBFDAdvanced.BinPackingResult result = BinPackingBFDAdvanced.packItemsBFD(items, binCapacity);end = System.currentTimeMillis();System.out.printf("高级BFD实现: %5dms, 箱子数: %d, 平均填充率: %.2f%%%n", end-start, result.bins.size(), result.getAverageFillRate()*100);}private static List<Integer> generateRandomItems(int count, int maxSize) {Random random = new Random();return IntStream.range(0, count).map(i -> random.nextInt(maxSize) + 1).boxed().toList();}
}

5. 应用场景与扩展

5.1 实际应用案例

  1. 物流运输：

    • 集装箱装载优化
    • 卡车货物配载
    • 航空货运管理

  2. 云计算：

    • 虚拟机分配
    • 容器调度
    • 资源分配

  3. 生产制造：

    • 原材料切割
    • 生产任务调度
    • 仓库货架管理

5.2 算法扩展变种

  1. 多维BFD：

    • 考虑物品的多个维度(长、宽、高)
    • 实现方式：扩展Bin类，添加多维容量检查

  2. 动态BFD：

    • 处理动态到达的物品流
    • 实现方式：结合在线算法策略

  3. 成本感知BFD：

    • 不同箱子有不同的使用成本
    • 实现方式：在选择箱子时考虑成本因素

  4. 带约束的BFD：

    • 某些物品不能放在一起
    • 实现方式：添加冲突检查逻辑

6. 与其他算法对比

6.1 BFD vs FFD

特性BFDFFD
选择策略剩余空间最小的合适箱子第一个能装下的箱子
空间利用率通常更高略低
时间复杂度O(n²)或O(n log n)O(n²)或O(n log n)
实现复杂度稍复杂较简单
适用场景对空间利用率要求高的场景一般场景

6.2 BFD与其他算法对比

  1. Next Fit (NF)：

    • 只检查当前箱子，无法回溯
    • 效率低但实现简单

  2. First Fit (FF)：

    • 选择第一个能装下的箱子
    • 比BFD快但空间利用率低

  3. Worst Fit (WF)：

    • 选择剩余空间最大的箱子
    • 适合希望均匀分布负载的场景

7. 完整Java实现(综合版)

import java.util.*;
import java.util.stream.Collectors;/*** 完整的BFD算法实现，包含所有优化和功能*/
public class ComprehensiveBFD {public static void main(String[] args) {// 示例使用List<Integer> items = generateItems(20, 10);int binCapacity = 10;System.out.println("物品列表: " + items);BFDResult result = pack(items, binCapacity);result.printAnalysis();}/*** BFD装箱结果类*/public static class BFDResult {private final List<Bin> bins;private final int binCapacity;private final long packingTime;public BFDResult(List<Bin> bins, int binCapacity, long packingTime) {this.bins = bins;this.binCapacity = binCapacity;this.packingTime = packingTime;}public int getBinCount() {return bins.size();}public double getAverageFillRate() {return bins.stream().mapToDouble(bin -> (double)bin.getUsedCapacity() / binCapacity).average().orElse(0);}public double getEfficiency() {int totalItems = bins.stream().mapToInt(bin -> bin.getItems().size()).sum();return (double)totalItems / (bins.size() * binCapacity);}public void printAnalysis() {System.out.println("\n装箱分析结果:");System.out.printf("箱子数量: %d\n", getBinCount());System.out.printf("平均填充率: %.2f%%\n", getAverageFillRate() * 100);System.out.printf("算法效率: %.4f\n", getEfficiency());System.out.printf("计算时间: %dms\n", packingTime);System.out.println("\n箱子详情:");bins.forEach(bin -> {System.out.printf("箱子 %2d: %s (使用率: %5.2f%%)%n",bins.indexOf(bin)+1, bin.getItems().stream().map(String::valueOf).collect(Collectors.joining(", ", "[", "]")),(double)bin.getUsedCapacity() / binCapacity * 100);});}}/*** 箱子类*/public static class Bin {private final List<Integer> items;private int usedCapacity;public Bin() {this.items = new ArrayList<>();this.usedCapacity = 0;}public boolean canAdd(int item, int binCapacity) {return usedCapacity + item <= binCapacity;}public void addItem(int item) {items.add(item);usedCapacity += item;}public List<Integer> getItems() {return Collections.unmodifiableList(items);}public int getUsedCapacity() {return usedCapacity;}}/*** 装箱方法*/public static BFDResult pack(List<Integer> items, int binCapacity) {long startTime = System.currentTimeMillis();// 验证输入validateInput(items, binCapacity);// 排序物品(降序)List<Integer> sortedItems = new ArrayList<>(items);sortedItems.sort(Collections.reverseOrder());List<Bin> bins = new ArrayList<>();// 使用TreeMap优化查找: key=剩余容量, value=箱子索引列表TreeMap<Integer, List<Integer>> remainingMap = new TreeMap<>();for (int item : sortedItems) {// 查找最小剩余容量 >= item的箱子Map.Entry<Integer, List<Integer>> entry = remainingMap.ceilingEntry(item);if (entry != null) {// 获取第一个匹配的箱子int binIndex = entry.getValue().get(0);Bin bin = bins.get(binIndex);// 更新TreeMapupdateTreeMap(remainingMap, bin, binIndex, item, binCapacity);// 添加物品到箱子bin.addItem(item);} else {// 创建新箱子Bin newBin = new Bin();newBin.addItem(item);bins.add(newBin);// 计算并添加剩余容量到TreeMapint remaining = binCapacity - item;if (remaining > 0) {remainingMap.computeIfAbsent(remaining, k -> new ArrayList<>()).add(bins.size() - 1);}}}long endTime = System.currentTimeMillis();return new BFDResult(bins, binCapacity, endTime - startTime);}private static void updateTreeMap(TreeMap<Integer, List<Integer>> map, Bin bin, int binIndex, int item, int binCapacity) {// 移除旧的剩余容量记录int oldRemaining = binCapacity - (bin.getUsedCapacity() - item);List<Integer> indices = map.get(oldRemaining);if (indices != null) {indices.remove(Integer.valueOf(binIndex));if (indices.isEmpty()) {map.remove(oldRemaining);}}// 添加新的剩余容量记录int newRemaining = binCapacity - bin.getUsedCapacity();if (newRemaining > 0) {map.computeIfAbsent(newRemaining, k -> new ArrayList<>()).add(binIndex);}}private static void validateInput(List<Integer> items, int binCapacity) {if (binCapacity <= 0) {throw new IllegalArgumentException("箱子容量必须为正数");}for (int item : items) {if (item <= 0) {throw new IllegalArgumentException("物品大小必须为正数");}if (item > binCapacity) {throw new IllegalArgumentException("存在物品大小超过箱子容量");}}}private static List<Integer> generateItems(int count, int maxSize) {return new Random().ints(count, 1, maxSize + 1).boxed().collect(Collectors.toList());}
}

8. 总结

最佳适应递减算法(BFD)是解决装箱问题的高效算法：

  1. 排序+贪心：通过先排序再贪心选择，实现高效装箱
  2. 空间利用率高：通常比FFD获得更好的装箱结果
  3. 灵活可扩展：可适应多种变种问题
  4. 平衡效率：在时间复杂度和空间利用率间取得良好平衡

在实际应用中，BFD算法特别适合：

  • 对空间利用率要求高的场景
  • 物品大小差异较大的情况
  • 需要高质量近似解的场合

通过Java实现时，使用TreeSet/TreeMap等数据结构可以显著提高算法效率，特别是在处理大规模数据时。

更多资源：

https://www.kdocs.cn/l/cvk0eoGYucWA

本文发表于【纪元A梦】！

http://www.lryc.cn/news/2401445.html

相关文章：

  • C#学习第27天：时间和日期的处理
  • 编程技能：格式化打印05，格式控制符
  • MPLAB X IDE ​软件安装与卸载
  • windows编程实现文件拷贝
  • [6-01-01].第12节：字节码文件内容 - 属性表集合
  • 基于机器学习的水量智能调度研究
  • 深度解码：我如何用“结构进化型交互学习方法”与AI共舞，从学习小白到构建复杂认知体系
  • 深入浅出 Scrapy：打造高效、强大的 Python 网络爬虫
  • ES6 Promise 状态机
  • Axure 与 Cursor 集成实现方案
  • 汽车加气站操作工证考试重点
  • 贪心算法应用：带权任务间隔调度问题详解
  • 用电脑控制keysight示波器
  • LLaMA-Factory - 批量推理（inference）的脚本
  • React从基础入门到高级实战：React 高级主题 - 测试进阶：从单元测试到端到端测试的全面指南
  • Ansible 剧本精粹 - 编写你的第一个 Playbook
  • 【Elasticsearch】Elasticsearch 核心技术（二）：映射
  • 【计算机网络】网络层协议
  • .NET Core接口IServiceProvider
  • 结构型设计模式之Proxy（代理）
  • 案例分享--汽车制动卡钳DIC测量
  • Redis Set集合命令、内部编码及应用场景(详细)
  • C++算法动态规划1
  • 【快速预览经典深度学习模型：CNN、RNN、LSTM、Transformer、ViT全解析！】
  • KaiwuDB在边缘计算领域的应用与优势
  • 如何避免二极管过载？
  • Vue.js组件开发系统性指南
  • React---day9
  • 设计模式 - 模板方法模式
  • 鸿蒙开发List滑动每项标题切换悬停