将蓝盒子包装成红盒子以优化成本具有挑战性

Question

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

• ，一个蓝色的盒子b1的运输成本是COST1，蓝色盒B2，cost2并相应地对蓝盒B3是COST3。

• 我们可以使用任意尺寸组合的任意数量的蓝色方块，但目标是最小化运输成本。所以这意味着，如果我们考虑将多个红色框（各种尺寸可能）放在蓝色框中，如果它们合适的话。 我们认为最大的红盒子可以很容易地贴合在蓝框B1除了 COST1之间的关系.. COST3如下：

  COST1 = 2 * cost2 = 3 * COST3。

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

现在你会怎样解决这个问题？

Answer 1

要开始你可以使用树形图或kd树，你可以在这里找到一个例子：http://www.blackpawn.com/texts/lightmaps/default.html。 也许您可以将其与例如first-fit的装箱算法结合使用。