將藍盒子包裝成紅盒子以優化成本具有挑戰性

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的裝箱算法結合使用。