当前位置：Gxlcms > PHP教程 > php解决装箱问题

php解决装箱问题

时间：2021-07-01 10:21:17 帮助过：20人阅读

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

)
  1. // php 练习 之装箱问题
  2. // author: mx (http://my.oschina.net/meikaiyuan)
  3. // 2013/5/30
  5. // 问题：
  6. // http://www.oschina.net/question/117304_112681
  7. /*
  8. 题目：
  10. 以前问过类似问题，没有很好解答。所以想再问一次。
  12. 有大大小小的一堆石头要用船拉到河对岸
  13. --石头有m块，每块的重量已知
  14. --船每次只能装k块石头，并且装载重量不可以超过w
  15. --想求出最少几趟能把全部石头运过河。
  17. ------------------------------------
  18. 例1
  19. 石头有9块，重量分别是1,2,3,4,5,6,7,8,9
  20. k=3
  21. w=15
  22. 那么结果是，最少3次就可以运完。
  23. ------------------------------------
  24. 例2
  25. 石头有9块，重量分别是1,1,1,5,6,6,7,9,9
  26. k=3
  27. w=15
  28. 那么结果是，最少 4 次才可以运完。
  29. */
  31. //代码开始
  33. //石头
  34. global $rocks;
  35. // 船每次最多装几块
  36. global $k;
  37. // 船最大载重量
  38. global $w;
  40. $k=3;
  41. $rocks=array(1,2,3,4,5,6,7,8,9);
  42. // $rocks=array(1,1,1,5,6,6,7,9,9); //换成这组数据试试结果？
  43. $w=15;
  45. // 当前运了几次
  46. $count=0;
  47. // 运输过程,二维数组，形如 1=>array(9,5,1)，表示第几次运了哪一些
  48. $process=array();
  50. // 求数组$rocks中一组合，使得最多$k个元素且这些元素的和尽可能大但小于等于指定值$w, 数组已经按从大到小排序过
  51. function getMaxCombination( ) {
  52. //石头
  53. global $rocks;
  54. // 船每次最多装几块
  55. global $k;
  56. // 船最大载重量
  57. global $w;
  59. // 保存各种$k下满足所有元素之和小于等于w且最大的集合
  60. $k_w_result=array();
  61. // 最大组合值
  62. $max_sum=0;
  63. // 哪项最大
  64. $max_one=0;
  66. for ($start=$k;$start>0;$start--){
  67. // 找到由固定$start个元素组成的最大解
  68. $start_w_arr = getMaxCombination2($start);
  69. echo "寻找由 $start 个元素组成的最大解: \n";
  70. print_r($start_w_arr);
  71. echo "\n";
  72. $sum=array_sum( $start_w_arr );
  73. // 注意：因为是降序排列的，$k--, 越早找到的同sum的组合$k越大，也就是解越好，所以是小于不是小于等于
  74. if($sum>$max_sum){
  75. $max_sum=$sum;
  76. $max_one=$k-$start;
  77. }
  78. $k_w_result[]= $start_w_arr ;
  79. }
  80. return $k_w_result[$max_one];
  81. }
  83. // 求数组$rocks中一由给定$start个元素构成的组合，这些元素的和尽可能大但小于等于指定值$w, 数组已经按从大到小排序过
  84. function getMaxCombination2($start ) {
  85. //石头们
  86. global $rocks;
  87. // 船每次最多装几块
  88. global $k;
  89. // 船最大载重量
  90. global $w;
  92. if(count($rocks)<$start){
  93. return array(0);
  94. }
  95. $c=count($rocks);
  96. // 根据$start生成一函数，内含$start层for循环代码, 然后包含进来再调用此函数
  97. if(!file_exists( "$start.php")){
  98. $output_1="";
  99. $output_2='$sum=';
  100. $output_3='if($sum<=$w){ $arr=array(); ';
  101. $output_4='';
  102. for($i=0;$i<$start;$i++){
  103. $output_1.='for($p'.$i.'='.$i.';$p'.$i.'<$c-'.($start-$i-1).';$p'.$i.'++){'."\n";
  104. if($i>0){
  105. $output_2.='+';
  106. }
  107. $output_2.='$rocks[$p'.$i.']';
  108. $output_3.='$arr[]=$rocks[$p'.$i.'];';
  109. $output_4.='}';
  110. }
  111. $output_2.=';';
  112. $output_3.=' return $arr; }' ;
  113. $output='';
  115. file_put_contents("$start.php",$output);
  116. include_once "$start.php";
  117. }
  118. else{
  119. include_once "$start.php";
  120. }
  121. return call_user_func('myfor'.$start ,$rocks,$c,$w);
  122. }
  124. //开始计算
  125. // 数组先从大到小排序, 此操作是后续算法省时省力的关键
  126. rsort($rocks);
  128. // 为了防止石头过大船过小造成下面算法死循环
  129. foreach ($rocks as $v){
  130. if($v>$w){
  131. die("有石头不可能装船，换大船来再战！");
  132. }
  133. }
  135. // 算法开始
  136. while(!empty($rocks)){
  137. // 开始装一船
  138. $process[$count]=array();
  140. // 装船
  141. $process[$count]= getMaxCombination( ) ;
  143. // 从石头中移除已经装船的
  144. foreach($process[$count] as $v){
  145. $key=array_search($v, $rocks);
  146. unset( $rocks[$key]);
  147. }
  148. $rocks=array_values($rocks);
  149. // 装船数+1
  150. $count++;
  151. }
  152. // 输出结果
  153. echo '最小次数:'.$count."\n";
  155. echo '装船过程:';
  156. print_r($process);
  158. ?>

人气教程排行

本站所有资源全部来源于网络，若本站发布的内容侵害到您的隐私或者利益，请联系我们删除！