2545 9-8 装箱问题的近似算法Best Fit
题目描述
设有体积分别为v1 ,v 2,…… ,vn 的 n 种物品要装入容量为 c 的箱子里。不同的装箱方案所需的箱子数可能不同。装箱问题要求找出一种装完这n 种物品所需的箱子数最少的装箱方案。装箱问题的近似算法Best Fit 的基本思想是，n 种物品依次装箱，将物品i 装入箱子j应满足
，即选取第j号箱子，使得装入物品i后所留空隙最小。其中k c 表示已装入第k号箱子的物品的体积。
设计并实现装箱问题的近似算法Best Fit。
输入格式:
输入数据第一行有2 个正整数n和c，分别表示有n种物品要装入容量为c的箱子里。接下来的1行中，有n个正整数分别表示n种物品的体积。
输出格式:
将计算出的最少箱子数输出
输入样例 复制
10 6 3 4 4 3 5 1 2 5 3 1
输出样例
复制
6
