algorithm - 如何以最节省空间的方式选择 DVD 的内容？

我有这些目录，A、B、C.. 我需要在 DVD 上刻录各种大小。问题是我不想浪费任何空间。我想将这些目录尽可能紧密地打包在 DVD 中，而不考虑顺序。当然，目录的内容是不可干预的。

例如：DVD 是 4GB。A 为 1GB，B 为 2GB，C 为 3GB，D 为 2GB。

按照订单，我需要 3 张 DVD{1: [A,B], 2: [C], 3: [D]}

但最有效的方法是 2 张 DVD{1: [B, D], 2: [A,C]}

很难从哪里开始。是否已经有一个算法？

我正在研究 Python 3，但欢迎使用通用代码。

标签： algorithm

这是一个 NP Hard 的装箱问题，因此找到一个准确的答案将花费大量时间。您可以使用简单的背包算法，但它可能并不总是正确的。这是一个链接，它更详细地解释了这一点。