php解決裝箱問題

我對裝箱問題，石頭過河問題的解法
見http://www.oschina.net/question/117304_112681

實現思路主要為：
1. 大塊石頭必須優先裝箱（早裝和留到後面裝都要裝，先解決之）
2. 優先裝重量接近w的
3. 同樣重量優先裝多塊，如裝9,6和裝9,5 ,1比，則優先951裝箱
4. 使用php的函數以簡化程式碼，並使用根據k值產生函數的技巧
5. 此類問題由於本身性質，計算量較大，請酌情設定參數測試。

範例輸出：（當rocks為1~9，w為15，k為3）
尋找由3 個元素組成的最大解:
Array
(
[ 0] => 9
[1] => 5
[2] => 1
)

尋找由2 個元素組成的最大解:
Array
(
[0] => 9
[1] => 6
)

找出由1 個元素組成的最大解:
Array
(
[0] => 9
)

尋找由3 個元素組成的最大解:
Array
(
[0] => 8
[1] = > 4
[2] => 3
)

尋找由2 個元素組成的最大解:
Array
(
[0] => 8
[1] => 7
)

尋找由1 個元素組成的最大解:
Array
(
[0] => 8
)
(
[0] => 8
)

尋找由3 個元素組成的最大解:
Array
(
[0] => 7
[1] => 6
[2] => 2
)

尋找由2 個元素組成的最大解:
Array
(
[0] => 7
[1] => 6
)

尋找由1 個元素組成的最大解:
Array
(
[0] => 7
)

最少次數:3
裝裝船過程:Array
(
[0] => Array
(
[0] => 9
[1] => 5
[2] => 1
)

[1] => Array
(
[0] => 8
[1] => 4
[2] => 3
)

[2] => Array
(
[0] => 7
[1] => 6
[2] => 2 ))

// php 練習之裝箱問題
// author: mx (http://my.oschina.net/meikaiyuan)
 // 2013/5/30

// 問題：
// http://www.oschina.net/question/117304_112681
/*
題目：


 以前問過類似問題，沒有很好解答。所以想再問一次。

有大大小小的一堆石頭要用船拉到河對岸
--石頭有m塊，每塊的重量已知
--船每次只能裝k塊石頭，並且裝載重量不可以超過w
--想求出最少幾趟能把全部石頭運過河。

 ------------------------------------
例1
石頭有9塊，重量分別是1,2,3,4,5,6,7,8,9
k=3
w=15
那麼結果是，最少3次就可以運完。
 ------------------------------------
 例2
 石頭有9塊，重量分別是1,1,1,5,6,6,7,9,9
k=3
w=15
那麼結果是，最少4 次才可以運完。
*/

//代碼開始

//石頭
global $rocks;
// 船隻每次最多裝幾塊
global $k;
// 船最大載重量
global $w;

$k=3;
$rocks=array(1,2,3,4,5,6,7,8 ,9);
// $rocks=array(1,1,1,5,6,6,7,9,9); //換成這組資料試試看結果？
$w=15;

// 目前運了幾下
$count=0;
// 運輸過程,二維數組，形如1=>array(9, 5,1)，表示第幾次運了哪一些
$process=array();

// 求數組$rocks中一組合，使得最多$k個元素且這些元素的和盡可能大但小於等於指定值$w, 數組已經按從大到小排序過
function getMaxCombination( ) {
 //石頭
 global $rocks;
 // 船每次最多裝幾塊
 global $k;
 // 船最大載重量
 global $w;

 // 保存各種$k下滿足所有元素總和小於等於w且最大的集合
 $k_w_result=array();
 // 最大組合值
 $max_sum=0;
 // 哪一項最大
 $max_one=0;

 for ($start=$k;$start>0;$start--){
 // 找出由固定$start個元素組成的最大解
 $start_w_arr = getMaxCombination2($start);
 echo "尋找由$start 個元素組成的最大解: n";
 print_r($start_w_arr);
 echo "n";
 $sum=array_sum( $start_w_arr );
 //注意：因為是降序排列的，$k--, 越早找到的同sum的組合$k越大，也就是解越好，所以是小於不是小於等於
 if($sum>$max_sum){
 $max_sum=$sum;
 $max_one=$k-$start;
 }
 $k_w_result[]= $start_w_arr ;
 }
 return $k_w_result[$max_one] ;
}

// 求數組$rocks中一由給定$start個元素構成的組合，這些元素的和盡可能大但小於等於指定值$w, 數組已經按從大到小排序過
function getMaxCombination2($start ) {
    //石頭們
	global $rocks;
	// 船每次最多裝幾塊
	global $k;
 // 船最大載重量
 global $w;

 if(count($rocks) return array(0);
 }
 $c= count($rocks);
 // 根據$start產生一函數，內含$start層for循環程式碼, 然後包含進來再呼叫此函數
 if(!file_exists( "$start.php")) {
 $output_1="";
 $output_2='$sum=';
 $output_3='if($sum $output_4='';
 for($i=0;$i $output_1.='for($p'.$i.'='.$i .';$p'.$i.' if( $i>0){
 $output_2.=' ';
 }
 $output_2.='$rocks[$p'.$i.']';
 $output_3.=' $arr[]=$rocks[$p'.$i.'];';
 $output_4.='}';
 }
 $output_2.=';';
 $ output_3.=' return $arr; }' ;
 $output='';

 file_put_contents("$start.php",$output);
 include_once "$start.php";
 }
 else{
 include_once "$start.php";
 }
 return call_user_func('myfor'.$start ,$rocks,$c,$w);
}

//開始開始計算
// 陣列先從大到小排序, 此操作是後續演算法省時省力的關鍵
rsort($rocks);

// 為了防止石頭過大船過小造成下面演算法死循環
foreach ($rocks as $v){
 if($v>$w){
 die("有石頭不可能裝船，換大船來再戰！ ");
 }
}

// 演算法開始
while(!empty($rocks)){
 // 開始裝一船
 $process[$ count]=array();

 // 裝船
 $process[$count]= getMaxCombination( ) ;

 // 從石頭中移除已經裝船的
 foreach($process[$count] as $v){
 $key=array_search($v, $rocks);
 unset( $rocks[$key]);
 }
 $ rocks=array_values($rocks);
 // 裝船數1
 $count ;
}
// 輸出結果
echo '最小次數:'.$count."n" ;

echo '裝船過程:';
print_r($process);