首页 > 代码库 > 关于近似装箱问题的思考。
关于近似装箱问题的思考。
有这样一个需求， 需要对一组元素进行打包（装箱），箱子的容积一定，但是至少可以装入一件物品，即使物品的体积大于箱子，求用最少的箱子装载。
该问题类似装箱。在对物体发货时候，可以达到最少的包裹数，挺有实际意义，借此研究一下装箱问题。下面代码是对与该问题的实现。由于是记录作用，文笔较为粗糙，后续修正加以详细说明。
该实现借鉴了装箱算法，关于装箱算法可以参考网络文章。如下：
http://blog.csdn.net/zhangnaigan/article/details/38352745
http://blog.csdn.net/x_i_y_u_e/article/details/46765093
具体实现代码如下：
$items = array( 0.1,0.3,0.8,0.4,0.5,0.2,1);//sort($items,SORT_DESC);defined(‘BOXSIZE‘) || define(‘BOXSIZE‘,1);function bestEncasement($items){ sort($items); $cnt = count($items,SORT_DESC);//更加有利于装箱 $box = array(); $dealArr = array(); for($j = 0;$j<$cnt;$j++){ $lastSize = intval(BOXSIZE); for($i = $cnt -1;$i>0;$i--){ if(in_array($i,$dealArr)){ continue;//如果该元素已经处理过则跳过 } //探测盒子是否为空 如果为空将元素加入 if(empty($box[$j])){ $box[$j][] = $items[$i]; $dealArr[] = $i; $lastSize -= $items[$i]; if($items[$i]>=BOXSIZE){ break;//空间已经存满直接跳出处理下一个盒子 } }else{ $tmpSize =$lastSize - $items[$i];//探测盒子是否够存放该元素 if($tmpSize == 0){ $box[$j][] = $items[$i]; $dealArr[] = $i; break;//存入空间剩余0 则跳出循环 处理下一个盒子 } if($tmpSize>0){//足够存入盒子 探测下一个元素 $box[$j][] = $items[$i]; $lastSize -= $items[$i]; $dealArr[] = $i; continue; }else{ //不足 处理下一个盒子 break; } } } } return $box;}print_r(bestEncasement($items));
关于近似装箱问题的思考。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。