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

贪心算法应用：装箱问题(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

特性	BFD	FFD
选择策略	剩余空间最小的合适箱子	第一个能装下的箱子
空间利用率	通常更高	略低
时间复杂度	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梦】！