如何以最高空间利用率打包不可拆分目录到DVD？求算法及实现

嘿，你碰到的这个问题其实是经典的装箱问题（Bin Packing Problem）——核心就是把不同体积的物品（这里就是你的目录）塞进容量固定的容器（DVD）里，要求用最少的容器，还不能拆分物品。这玩意儿属于NP难问题，意思是不存在能在短时间内算出绝对最优解的通用算法，但咱们可以用启发式算法拿到非常接近最优的结果，甚至在大多数日常场景里直接得到最优解。

常用的启发式算法推荐 #

最实用的当属**首次适应递减（First Fit Decreasing, FFD）**算法，思路很简单：

• 先把所有目录按大小从大到小排序
• 然后依次把每个目录放进第一个能装下它的DVD里

这种方法比按原始顺序瞎塞的效果好太多，比如你给的例子，用FFD就能直接得到仅需2张DVD的最优方案。

Python 实现代码 #

下面是通用的实现，支持自定义目录名称和大小，以及DVD容量：

def bin_packing_ffd(directories, dvd_capacity):
    # 按目录大小降序排序，保留原始名称
    sorted_dirs = sorted(directories.items(), key=lambda x: -x[1])
    dvds = []
    
    for dir_name, dir_size in sorted_dirs:
        # 尝试放入已有的DVD
        placed = False
        for dvd in dvds:
            current_total = sum(size for _, size in dvd)
            if current_total + dir_size <= dvd_capacity:
                dvd.append((dir_name, dir_size))
                placed = True
                break
        # 没找到合适的，新建一张DVD
        if not placed:
            dvds.append([(dir_name, dir_size)])
    
    # 整理成你要的格式：{DVD编号: [目录名称列表]}
    result = {idx + 1: [name for name, _ in dvd] for idx, dvd in enumerate(dvds)}
    return result

# 测试你的示例场景
if __name__ == "__main__":
    # 这里直接用GB作为单位，也可以换成字节（比如4*1024**3）更精准
    DVD_CAPACITY_GB = 4
    my_directories = {
        "A": 1,
        "B": 2,
        "C": 3,
        "D": 2
    }
    
    optimal_plan = bin_packing_ffd(my_directories, DVD_CAPACITY_GB)
    print("最优（近似）刻录方案：")
    for dvd_num, dirs in optimal_plan.items():
        print(f"DVD {dvd_num}: {dirs}")

代码说明 #

运行这段代码后，输出就是你想要的最优方案：

最优（近似）刻录方案：
DVD 1: ['C', 'A']
DVD 2: ['B', 'D']

完全符合你给出的最优结果。

如果你的目录数量很少，且追求绝对最优解，可以试试分支定界法，但这种方法效率很低，目录多了会慢得离谱。日常使用的话，FFD算法完全足够——既快，结果又几乎总是最优的。

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