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

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

1. 装箱问题概述

装箱问题(Bin Packing Problem)是计算机科学和运筹学中的一个经典组合优化问题。问题的描述如下：

给定一组物品，每个物品有一定的体积，以及若干容量相同的箱子，目标是用最少数量的箱子装下所有物品。

问题形式化描述

• 输入：
  • n个物品，每个物品有一个大小wᵢ，其中0 < wᵢ ≤ C（C为箱子容量）
  • 无限数量的箱子，每个箱子容量为C
• 输出：
  • 将n个物品分配到尽可能少的箱子中，且每个箱子中物品大小之和不超过C

2. 贪心算法简介

贪心算法(Greedy Algorithm)是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择，从而希望导致结果是全局最好或最优的算法。

对于装箱问题，常见的贪心算法策略有：

1. 首次适应算法(First Fit, FF)：将每个物品放入第一个能容纳它的箱子
2. 最佳适应算法(Best Fit, BF)：将每个物品放入能容纳它的最满的箱子
3. 首次适应递减算法(First Fit Decreasing, FFD)：先将物品按大小降序排序，然后使用首次适应算法
4. 最佳适应递减算法(Best Fit Decreasing, BFD)：先将物品按大小降序排序，然后使用最佳适应算法

本文将重点介绍**首次适应递减算法(FFD)**及其Java实现。

3. 首次适应递减算法(FFD)详解

3.1 算法思想

FFD算法是解决装箱问题最常用的启发式算法之一，其基本思想是：

1. 先将所有物品按体积从大到小排序
2. 然后依次处理每个物品，将其放入第一个能容纳它的箱子
3. 如果没有合适的箱子，则开启一个新箱子

3.2 算法步骤

1. 输入物品列表和箱子容量C
2. 将物品按体积从大到小排序
3. 初始化空的箱子列表
4. 对于每个物品：
   a. 遍历已有箱子，找到第一个能容纳该物品的箱子
   b. 如果找到，将物品放入该箱子
   c. 如果没有找到，创建一个新箱子并将物品放入
5. 返回使用的箱子列表

3.3 算法复杂度分析

• 排序阶段：O(n log n)，取决于排序算法
• 装箱阶段：最坏情况下为O(n²)，因为对于每个物品可能需要遍历所有箱子

3.4 算法性能

FFD算法有以下性能保证：

1. 对于任何输入，FFD使用的箱子数不超过(11/9)*OPT + 1，其中OPT是最优解
2. 对于大多数实际案例，FFD的表现非常接近最优解

4. Java实现FFD算法

4.1 基本实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinPackingFFD {

    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 = firstFitDecreasing(items, binCapacity);
        
        System.out.println("使用的箱子数量: " + bins.size());
        for (int i = 0; i < bins.size(); i++) {
            System.out.println("箱子 " + (i+1) + ": " + bins.get(i) + 
                             " (总大小: " + bins.get(i).stream().mapToInt(Integer::intValue).sum() + ")");
        }
    }
    
    public static List<List<Integer>> firstFitDecreasing(List<Integer> items, int binCapacity) {
        // 复制物品列表以避免修改原始数据
        List<Integer> sortedItems = new ArrayList<>(items);
        // 按降序排序
        sortedItems.sort(Collections.reverseOrder());
        
        List<List<Integer>> bins = new ArrayList<>();
        
        for (int item : sortedItems) {
            boolean placed = false;
            // 尝试将物品放入已有箱子
            for (List<Integer> bin : bins) {
                int currentBinWeight = bin.stream().mapToInt(Integer::intValue).sum();
                if (currentBinWeight + item <= binCapacity) {
                    bin.add(item);
                    placed = true;
                    break;
                }
            }
            // 如果没有合适的箱子，创建新箱子
            if (!placed) {
                List<Integer> newBin = new ArrayList<>();
                newBin.add(item);
                bins.add(newBin);
            }
        }
        
        return bins;
    }
}

4.2 优化实现

为了提高效率，我们可以预先计算并存储每个箱子的剩余容量：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinPackingFFDOptimized {

    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<Bin> bins = firstFitDecreasingOptimized(items, binCapacity);
        
        System.out.println("使用的箱子数量: " + bins.size());
        for (int i = 0; i < bins.size(); i++) {
            System.out.println("箱子 " + (i+1) + ": " + bins.get(i).items + 
                             " (总大小: " + bins.get(i).currentWeight + ")");
        }
    }
    
    static class Bin {
        List<Integer> items = new ArrayList<>();
        int currentWeight = 0;
        int capacity;
        
        Bin(int capacity) {
            this.capacity = capacity;
        }
        
        boolean canAdd(int item) {
            return currentWeight + item <= capacity;
        }
        
        void addItem(int item) {
            items.add(item);
            currentWeight += item;
        }
    }
    
    public static List<Bin> firstFitDecreasingOptimized(List<Integer> items, int binCapacity) {
        List<Integer> sortedItems = new ArrayList<>(items);
        sortedItems.sort(Collections.reverseOrder());
        
        List<Bin> bins = new ArrayList<>();
        
        for (int item : sortedItems) {
            boolean placed = false;
            for (Bin bin : bins) {
                if (bin.canAdd(item)) {
                    bin.addItem(item);
                    placed = true;
                    break;
                }
            }
            if (!placed) {
                Bin newBin = new Bin(binCapacity);
                newBin.addItem(item);
                bins.add(newBin);
            }
        }
        
        return bins;
    }
}

4.3 进一步优化：使用优先队列

我们可以使用优先队列来更高效地找到合适的箱子：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class BinPackingFFDWithPQ {

    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<Bin> bins = firstFitDecreasingWithPQ(items, binCapacity);
        
        System.out.println("使用的箱子数量: " + bins.size());
        for (int i = 0; i < bins.size(); i++) {
            System.out.println("箱子 " + (i+1) + ": " + bins.get(i).items + 
                             " (总大小: " + bins.get(i).currentWeight + ")");
        }
    }
    
    static class Bin implements Comparable<Bin> {
        List<Integer> items = new ArrayList<>();
        int currentWeight = 0;
        int capacity;
        
        Bin(int capacity) {
            this.capacity = capacity;
        }
        
        boolean canAdd(int item) {
            return currentWeight + item <= capacity;
        }
        
        void addItem(int item) {
            items.add(item);
            currentWeight += item;
        }
        
        // 按照剩余容量升序排列，这样我们可以优先尝试剩余容量多的箱子
        @Override
        public int compareTo(Bin other) {
            return Integer.compare(other.capacity - other.currentWeight, 
                                 this.capacity - this.currentWeight);
        }
    }
    
    public static List<Bin> firstFitDecreasingWithPQ(List<Integer> items, int binCapacity) {
        List<Integer> sortedItems = new ArrayList<>(items);
        sortedItems.sort(Collections.reverseOrder());
        
        List<Bin> bins = new ArrayList<>();
        PriorityQueue<Bin> pq = new PriorityQueue<>();
        
        for (int item : sortedItems) {
            Bin bin = pq.peek();
            if (bin != null && bin.canAdd(item)) {
                bin = pq.poll();
                bin.addItem(item);
                pq.offer(bin);
            } else {
                Bin newBin = new Bin(binCapacity);
                newBin.addItem(item);
                bins.add(newBin);
                pq.offer(newBin);
            }
        }
        
        return bins;
    }
}

5. 算法测试与验证

5.1 测试用例设计

为了验证我们的实现是否正确，我们可以设计以下测试用例：

1. 简单测试：少量物品，容易验证

   • 输入：[2, 3, 4, 5], 容量=7
   • 预期：2个箱子 [5,2]和[4,3]

2. 边界测试：

   • 所有物品大小相同
   • 单个物品正好装满一个箱子
   • 单个物品超过箱子容量（应抛出异常）

3. 随机测试：

   • 生成随机物品列表进行测试

4. 已知最优解测试：

   • 使用已知最优解的小规模问题

5.2 测试代码实现

import org.junit.Test;
import static org.junit.Assert.*;
import java.util.List;

public class BinPackingFFDTest {
    
    @Test
    public void testSimpleCase() {
        List<Integer> items = List.of(2, 3, 4, 5);
        int binCapacity = 7;
        
        List<List<Integer>> bins = BinPackingFFD.firstFitDecreasing(items, binCapacity);
        
        assertEquals(2, bins.size());
        assertTrue(bins.get(0).containsAll(List.of(5, 2)) || bins.get(1).containsAll(List.of(5, 2)));
        assertTrue(bins.get(0).containsAll(List.of(4, 3)) || bins.get(1).containsAll(List.of(4, 3)));
    }
    
    @Test
    public void testPerfectFit() {
        List<Integer> items = List.of(5, 5, 5, 5);
        int binCapacity = 10;
        
        List<List<Integer>> bins = BinPackingFFD.firstFitDecreasing(items, binCapacity);
        
        assertEquals(2, bins.size());
        for (List<Integer> bin : bins) {
            assertEquals(10, bin.stream().mapToInt(Integer::intValue).sum());
        }
    }
    
    @Test
    public void testSingleItem() {
        List<Integer> items = List.of(7);
        int binCapacity = 10;
        
        List<List<Integer>> bins = BinPackingFFD.firstFitDecreasing(items, binCapacity);
        
        assertEquals(1, bins.size());
        assertEquals(7, bins.get(0).stream().mapToInt(Integer::intValue).sum());
    }
    
    @Test(expected = IllegalArgumentException.class)
    public void testItemTooLarge() {
        List<Integer> items = List.of(11);
        int binCapacity = 10;
        
        BinPackingFFD.firstFitDecreasing(items, binCapacity);
    }
    
    @Test
    public void testEmptyInput() {
        List<Integer> items = List.of();
        int binCapacity = 10;
        
        List<List<Integer>> bins = BinPackingFFD.firstFitDecreasing(items, binCapacity);
        
        assertTrue(bins.isEmpty());
    }
}

6. 性能分析与优化

6.1 时间复杂度分析

1. 排序阶段：O(n log n)
2. 装箱阶段：
   • 基本实现：O(n²) - 对于每个物品，最坏情况下需要检查所有箱子
   • 优先队列优化：O(n log n) - 每次插入和提取操作都是O(log n)

6.2 空间复杂度分析

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

6.3 实际性能测试

我们可以编写性能测试代码来比较不同实现的性能：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class BinPackingPerformanceTest {
    
    public static void main(String[] args) {
        int numItems = 10000;
        int binCapacity = 100;
        List<Integer> items = generateRandomItems(numItems, binCapacity);
        
        // 预热
        firstFitDecreasing(new ArrayList<>(items), binCapacity);
        firstFitDecreasingOptimized(new ArrayList<>(items), binCapacity);
        firstFitDecreasingWithPQ(new ArrayList<>(items), binCapacity);
        
        // 测试基本实现
        long start = System.currentTimeMillis();
        List<List<Integer>> bins1 = firstFitDecreasing(new ArrayList<>(items), binCapacity);
        long end = System.currentTimeMillis();
        System.out.println("基本实现: " + (end - start) + "ms, 箱子数: " + bins1.size());
        
        // 测试优化实现
        start = System.currentTimeMillis();
        List<BinPackingFFDOptimized.Bin> bins2 = firstFitDecreasingOptimized(new ArrayList<>(items), binCapacity);
        end = System.currentTimeMillis();
        System.out.println("优化实现: " + (end - start) + "ms, 箱子数: " + bins2.size());
        
        // 测试优先队列实现
        start = System.currentTimeMillis();
        List<BinPackingFFDWithPQ.Bin> bins3 = firstFitDecreasingWithPQ(new ArrayList<>(items), binCapacity);
        end = System.currentTimeMillis();
        System.out.println("优先队列实现: " + (end - start) + "ms, 箱子数: " + bins3.size());
    }
    
    private static List<Integer> generateRandomItems(int numItems, int maxSize) {
        List<Integer> items = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < numItems; i++) {
            items.add(random.nextInt(maxSize) + 1); // 1到maxSize
        }
        return items;
    }
    
    // 这里需要包含前面三个实现的方法...
}

7. 应用场景与扩展

7.1 实际应用场景

装箱问题在现实世界中有许多应用：

1. 物流与运输：将货物装入集装箱或卡车
2. 资源分配：云计算中的虚拟机分配
3. 存储管理：文件存储到磁盘或内存中
4. 生产计划：任务分配到机器上
5. 广告投放：将广告分配到固定时长的广告位

7.2 变种与扩展

1. 多维装箱问题：物品有多个维度（长、宽、高）
2. 可变大小箱子：箱子大小可以不同
3. 成本最小化：不同箱子有不同的成本
4. 在线装箱问题：物品按顺序到达，必须立即分配
5. 带冲突的装箱问题：某些物品不能放在同一个箱子中

7.3 其他算法比较

虽然FFD是一个很好的启发式算法，但还有其他算法可以解决装箱问题：

1. 精确算法：

   • 分支限界法
   • 动态规划（适用于小规模问题）

2. 近似算法：

   • Next Fit (NF)
   • Worst Fit (WF)
   • Almost Worst Fit (AWF)

3. 元启发式算法（适用于大规模问题）：

   • 遗传算法
   • 模拟退火
   • 禁忌搜索

8. 完整Java实现示例

以下是结合了所有优化和功能的完整实现：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class AdvancedBinPackingFFD {
    
    public static void main(String[] args) {
        // 示例使用
        List<Integer> items = generateRandomItems(20, 10);
        int binCapacity = 10;
        
        System.out.println("物品列表: " + items);
        
        BinPackingResult result = packItems(items, binCapacity);
        
        System.out.println("使用的箱子数量: " + result.getBinCount());
        System.out.println("平均填充率: " + String.format("%.2f", result.getAverageFillRate() * 100) + "%");
        System.out.println("详细装箱情况:");
        result.printBins();
    }
    
    /**
     * 装箱结果类
     */
    public 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 int getBinCount() {
            return bins.size();
        }
        
        public double getAverageFillRate() {
            return bins.stream()
                    .mapToDouble(bin -> (double)bin.getCurrentWeight() / binCapacity)
                    .average()
                    .orElse(0);
        }
        
        public void printBins() {
            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 List<Bin> getBins() {
            return Collections.unmodifiableList(bins);
        }
    }
    
    /**
     * 箱子类
     */
    public static class Bin implements Comparable<Bin> {
        private final List<Integer> items = new ArrayList<>();
        private int currentWeight = 0;
        private final int capacity;
        
        public Bin(int capacity) {
            this.capacity = capacity;
        }
        
        public boolean canAdd(int item) {
            if (item > capacity) {
                throw new IllegalArgumentException("物品大小超过箱子容量");
            }
            return currentWeight + item <= capacity;
        }
        
        public void addItem(int item) {
            if (!canAdd(item)) {
                throw new IllegalStateException("无法将物品添加到箱子中");
            }
            items.add(item);
            currentWeight += item;
        }
        
        public List<Integer> getItems() {
            return Collections.unmodifiableList(items);
        }
        
        public int getCurrentWeight() {
            return currentWeight;
        }
        
        public int getRemainingCapacity() {
            return capacity - currentWeight;
        }
        
        @Override
        public int compareTo(Bin other) {
            // 按剩余容量降序排列
            return Integer.compare(other.getRemainingCapacity(), this.getRemainingCapacity());
        }
    }
    
    /**
     * 装箱方法
     */
    public static BinPackingResult packItems(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("存在物品大小超过箱子容量");
            }
        }
        
        // 复制物品列表以避免修改原始数据
        List<Integer> sortedItems = new ArrayList<>(items);
        // 按降序排序
        sortedItems.sort(Collections.reverseOrder());
        
        List<Bin> bins = new ArrayList<>();
        PriorityQueue<Bin> binQueue = new PriorityQueue<>();
        
        for (int item : sortedItems) {
            Bin bin = binQueue.peek();
            if (bin != null && bin.canAdd(item)) {
                bin = binQueue.poll();
                bin.addItem(item);
                binQueue.offer(bin);
            } else {
                Bin newBin = new Bin(binCapacity);
                newBin.addItem(item);
                bins.add(newBin);
                binQueue.offer(newBin);
            }
        }
        
        return new BinPackingResult(bins, binCapacity);
    }
    
    /**
     * 生成随机物品列表
     */
    public static List<Integer> generateRandomItems(int count, int maxSize) {
        List<Integer> items = new ArrayList<>();
        java.util.Random random = new java.util.Random();
        for (int i = 0; i < count; i++) {
            items.add(random.nextInt(maxSize) + 1); // 1到maxSize
        }
        return items;
    }
}

9. 总结

首次适应递减算法(FFD)是解决装箱问题的一种高效启发式算法，通过先将物品按大小降序排序，然后使用首次适应策略，能够在大多数情况下得到接近最优的解。本文详细介绍了：

1. 装箱问题的定义和贪心算法的基本概念
2. FFD算法的详细思想和实现步骤
3. 多种Java实现方式，包括基本实现、优化实现和使用优先队列的实现
4. 测试用例设计和性能分析方法
5. 实际应用场景和算法扩展

FFD算法的时间复杂度主要取决于排序阶段(O(n log n))和装箱阶段(O(n²)或优化后的O(n log n))，在实际应用中表现良好。对于需要更高精度的场景，可以考虑结合其他优化算法或精确算法。

更多资源：

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

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