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

Question

我有这些不同大小的目录 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，但欢迎使用通用代码。

Answer 1

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

https://www.geeksforgeeks.org/bin-packing-problem-minimize-number-of-used-bins/