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
)

)

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) return array(0);
93. }
94. $c=count($rocks);
95. // 根据$start生成一函数，内含$start层for循环代码, 然后包含进来再调用此函数
96. if(!file_exists( "$start.php")){
97. $output_1="";
98. $output_2='$sum=';
99. $output_3='if($sum $output_4='';
100. for($i=0;$i $output_1.='for($p'.$i.'='.$i.';$p'.$i.' if($i>0){
101. $output_2.='+';
102. }
103. $output_2.='$rocks[$p'.$i.']';
104. $output_3.='$arr[]=$rocks[$p'.$i.'];';
105. $output_4.='}';
106. }
107. $output_2.=';';
108. $output_3.=' return $arr; }' ;
109. $output='';
111. file_put_contents("$start.php",$output);
112. include_once "$start.php";
113. }
114. else{
115. include_once "$start.php";
116. }
117. return call_user_func('myfor'.$start ,$rocks,$c,$w);
118. }
120. //开始计算
121. // 数组先从大到小排序, 此操作是后续算法省时省力的关键
122. rsort($rocks);
124. // 为了防止石头过大船过小造成下面算法死循环
125. foreach ($rocks as $v){
126. if($v>$w){
127. die("有石头不可能装船，换大船来再战！");
128. }
129. }
131. // 算法开始
132. while(!empty($rocks)){
133. // 开始装一船
134. $process[$count]=array();
136. // 装船
137. $process[$count]= getMaxCombination( ) ;
139. // 从石头中移除已经装船的
140. foreach($process[$count] as $v){
141. $key=array_search($v, $rocks);
142. unset( $rocks[$key]);
143. }
144. $rocks=array_values($rocks);
145. // 装船数+1
146. $count++;
147. }
148. // 输出结果
149. echo '最小次数:'.$count."\n";
151. echo '装船过程:';
152. print_r($process);
154. ?>

复制代码