php解决装箱问题 -php教程-PHP中文网

php解决装箱问题

WBOY

发布： 2016-07-25 08:51:00

原创

1190 人浏览过

我对装箱问题，石头过河问题的解法
见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 练习之装箱问题
// 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);
?>

复制代码