设有许多盒子,每个盒子都能容纳总重量C和物品i1,i2,i3, ... iN,它们分别重w1,w2,w3,...wN。现在想要把所有物品包装起来,但任一盒子都不能放置超过其容量的重物,而且要使用尽量少的盒子。例如,若C=5,物品分别重2,2,3,3,则我们可以用两个盒子解决该问题。
一般来说,这个问题很难,没有已知的有效的解决方法。编写一个程序,有效地实现下列各近似策略:
a. 将物品放入能够承受起重量的第一个盒子内(如果没有盒子拥有足够的容量就开辟一个新的盒子)。(该策略以及后面所有的策略都将得出3个盒子,这不是最优结果)
b. 把物品放入对其有最大容量的盒子内。
c. 把物品放入能够容纳下它而又不过载的装填的最满的盒子中
d. 这些策略中有通过将物品按重量预先排序而功能得到增强的吗?