【php】10kg入る箱3つに詰めたい
問題
10kgまで入る箱があって、商品（複数）を、3箱以内に梱包できるかチェックしたい。
商品が、1kg, 2kg, 3kg, 4kg, 5kg, 6kg, 7kg あったら、
箱1 => [4, 6]
箱2 => [3, 7]
箱3 => [1, 2, 5]
のように詰めることができるならOKとかの判定をしたい。
問題
総当りで試せば、一応、答えは出る。
ただ、箱に詰める商品の数が8,9個あたりを越えると計算量が半端なく多いためか、使い物にならないレベルで時間がかかるようになっていくので注意。順列を作るところでもうだめ。。。
大量に高速に判断する場合は、何らかの近似アルゴリズムで判断していくことになると思います。
総当りするのは、商品数が少ないとき限定で使うのがよいです。
総当り source
<?php
/**
* 順列を作る関数
*/
function pat($a, $s = array())
{
$r = array();
if (count($a) && is_array($a)) {
foreach ($a as $k => $v) {
$_s = array_merge($s, array($v));
$_a = $a;
unset($_a[$k]);
$_r = pat($_a, $_s);
$r = array_merge($r, $_r);
}
} else {
$r[] = $s;
}
return $r;
}
/**
* 箱詰めする関数
*
* 第1引数（配列）$aの商品を
* 第2引数（数値）$lまで入る箱に詰める
* 答えは複数ありうるけど、全部試して、一番箱数の少なかった結果を代表で返す
*/
function hakodume($a, $l)
{
//結果候補（1箱に1つ入れるとこうなるのだが、もっと詰めれるはず）
$r = $a;
//箱詰めの全部の順番を作る
$p = pat($a);
//全ての順番を試すループ
foreach ($p as $pv) {
//1箱目を用意
$x = array(array());
//箱に入れたいものでループ
foreach ($pv as $v) {
//箱に入らないものがあれば即座にやめる（無限ループ防止）
if ($v > $l) {
return false;
}
//これを入れると今の箱がいっぱいになるなら新しい箱を用意する
if (array_sum($x[0]) + $v > $l) {
array_unshift($x, array());
}
//今の箱に入れる
$x[0][] = $v;
}
//箱数がより少ない方に結果を差し替える
if (count($r) > count($x)) {
$r = $x;
}
}
//結果を返す
return $r;
}
実行例
1kg, 2kg, 3kg, 4kg, 5kg, 6kg, 7kg を、10kg箱に詰めるには？
<?php var_export(hakodume(array(1, 2, 3, 4, 5, 6, 7), 10)); ?>
array (
0 =>
array (
0 => 4,
1 => 6,
),
1 =>
array (
0 => 3,
1 => 7,
),
2 =>
array (
0 => 1,
1 => 2,
2 => 5,
),
)
実行例
1kg, 2kg, 3kg, 4kg, 5kg, 6kg, 7kg, 8kg, 9kg, 10kg を、10kg箱に詰めるには？
<?php var_export(hakodume(array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 10)); ?>
→ 10箱あると、30秒以上かかるみたいです (T-T
応用
箱に詰められる重量に加えて、用意できる箱の数の上限も引数に追加して、そもそも無理な場合やチェックする必要がないほど商品が多い場合などの計算を省けるようにすると少しは計算が速くなる。
希望の箱数以内に収まるならtrue、収まらないならfalseといった返事をさせることもできる。
3個以内に収まるか確認したいだけのときは、最初に答えが見つかった時点で終了させることもできる。
試した詰め方をすべて配列にして返させることもできる。
参考
ビンパッキング問題
ナップザック問題
NP困難問題