`n` 袋沙子并插入盒子,算法

`n` bag of sand and inserting into Box, Algorithms

我们有 n 袋沙子,体积为 v_1 to v_n(对于所有 i,0 < v_i < 1,但基本上没有排序)。我们想把所有的包都放在体积为 1 的盒子里。我们提出了一种算法。

at first we place all bags in the original order. then we select one box and place on it, bag 1, 2, 3,... until these can be place in box. if the i'th bag couldent be inserted in box, we choose another box and place it i'th, i+1'th and... until these can be place in the box.

如果使用的盒数为X,并且以最小方式(通过使用最小算法)使用的盒数为Y,为什么总是X < 2 * Y。

在你的最终分布中,连续盒子的体积总和大于1。特别是,对于每个i,盒子2*i和2*i+1的体积总和大于1。因此 X/2 <(每个 vi 的总和)和(每个 vi 的总和)<= Y.qed