见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
)
) 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);?>
复制代码