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
)

寻找由 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
// 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)<$start){
			return array(0);
	}
	$c=count($rocks); 
	//  根据$start生成一函数，内含$start层for循环代码, 然后包含进来再调用此函数
		if(!file_exists( "$start.php")){
		$output_1="";
		$output_2='$sum=';
		$output_3='if($sum<=$w){ $arr=array(); ';
		$output_4='';
		for($i=0;$i<$start;$i++){
			$output_1.='for($p'.$i.'='.$i.';$p'.$i.'<$c-'.($start-$i-1).';$p'.$i.'++){'."\n";
			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='<?php function myfor'.$start.'($rocks,$c,$w){ '.$output_1.$output_2.$output_3.$output_4 .' } ?>';
		
		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);

?>