将红盒包装在蓝盒中以优化成本是具有挑战性的

Question

这主要是包装问题： 假设有 20 个不同尺寸 r1 到 r8 的红色盒子（因此每个尺寸可能存在多个），这些盒子应该使用有 3 种尺寸 b1、b2 和 b3 的蓝色包装盒运输。

• 无论重量如何，蓝色盒子b1的运输成本是成本1，蓝色盒子b2的运输成本是成本2，因此蓝色盒子b3的运输成本是成本3。

• 我们可以使用任意数量、任意尺寸组合的蓝盒子，但目标是最大限度地降低运输成本。所以这意味着，如果我们考虑将多个红色盒子（可能有不同尺寸）放入蓝色盒子中（如果它们合适的话）。 我们假设最大的红色盒子可以很容易地放入蓝色盒子 b1 以及之间的关系 成本1,..成本3如下：

  成本1=2*成本2=3*成本3。

• 为了简单起见，我们可以选择任意值来定义每个红色框的尺寸，如果需要，也可以选择蓝色框的尺寸。

现在你会采取什么方法来解决这个问题？

Answer 1

首先，您可以使用树状图或 kd 树，您可以在此处找到示例：http://www.blackpawn.com/texts/lightmaps/default.html。 也许您可以将其与装箱算法结合起来，例如首次适应。