php解決裝箱問題-php教程-PHP中文網

php解決裝箱問題

WBOY

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

原創

1192 人瀏覽過

我對裝箱問題，石頭過河問題的解法
見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);

複製代碼