Home Backend Development PHP Tutorial php solves boxing problem

php solves boxing problem

Jul 25, 2016 am 08:51 AM



My solution to the boxing problem and the stone crossing problem
See http://www.oschina.net/question/117304_112681

The main implementation ideas are:
1. Large stones must be packed first (early loading and reserved until later) All the later items must be packed, so solve them first)
2. Priority is given to packing items with a weight close to w
3. Priority is given to packing multiple pieces of the same weight, such as 9,6 and 9,5,1, then 951 packing is preferred
4. Use PHP functions to simplify the code, and use the technique of generating functions based on k values ​​
5. Due to the nature of this type of problem, the calculation amount is large, please set up parameter tests as appropriate.

Example output: (when rocks is 1~9, w is 15, k is 3)
Find the maximum solution consisting of 3 elements:
Array
(
[0] => 9
[1] => 5
[2] => 1
)

Find the maximum solution consisting of 2 elements:
Array
(
[0] => 9
[1] => 6
)

Find the maximum solution consisting of 1 element Maximum solution:
Array
(
[0] => 9
)

Find the maximum solution consisting of 3 elements:
Array
(
[0] => 8
[1] => 4
[2] => 3
)

Find the maximum solution consisting of 2 elements:
Array
(
[0] => 8
[1] => 7
)

Find the maximum solution consisting of 1 element:
Array
(
[0] => 8
)

Finds the maximum solution consisting of 3 elements:
Array
(
[0] => 7
[1] => 6
[2] => 2
)

Find the maximum solution consisting of 2 elements:
Array
(
[0] => 7
[1] => 6
)

Find the maximum solution consisting of 1 element:
Array
(
[0] => 7
)

Minimum times: 3
Shipping process: 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 exercise boxing problem
  2. // author: mx (http://my.oschina.net/meikaiyuan)
  3. // 2013/5/30
  4. // Question:
  5. // http://www.oschina.net/question/117304_112681
  6. /*
  7. Title:
  8. I have asked similar questions before, but there is no good answer. So I want to ask again.
  9. There is a pile of large and small stones that need to be pulled to the other side of the river by boat
  10. --There are m pieces of stone, and the weight of each piece is known
  11. --The boat can only load k stones at a time, and the loading weight cannot exceed w
  12. --I want to find out the minimum number of trips that can transport all the stones across the river.
  13. ------------------------------------
  14. Example 1
  15. There are 9 stones, their weights are 1,2,3,4,5,6,7,8,9
  16. k=3
  17. w=15
  18. The result is that it can be shipped in at least 3 times.
  19. ------------------------------------
  20. Example 2
  21. There are 9 stones, each weighing 1 ,1,1,5,6,6,7,9,9
  22. k=3
  23. w=15
  24. The result is that it takes at least 4 times to complete the shipment.
  25. */
  26. //Code starts
  27. //Stones
  28. global $rocks;
  29. //The maximum number of pieces the ship can load at a time
  30. global $k;
  31. //The maximum load capacity of the ship
  32. global $w;
  33. $k =3;
  34. $rocks=array(1,2,3,4,5,6,7,8,9);
  35. // $rocks=array(1,1,1,5,6,6,7, 9,9); //Change to this set of data and try the result?
  36. $w=15;
  37. //How many times has it been shipped currently?
  38. $count=0;
  39. //Transportation process, two-dimensional array, in the shape of 1=>array(9,5,1), indicating how many times it has been shipped What luck did you have?
  40. $process=array();
  41. // Find a combination in the array $rocks so that there are at most $k elements and the sum of these elements is as large as possible but less than or equal to the specified value $w. The array has been pressed from Sorted from big to small
  42. function getMaxCombination( ) {
  43. //Stones
  44. global $rocks;
  45. //How many pieces can the ship carry at most? global $k;
  46. //The maximum load capacity of the ship
  47. global $w;
  48. / / Save the largest set under various $k that the sum of all elements is less than or equal to w and is the largest
  49. $k_w_result=array();
  50. // Maximum combination value
  51. $max_sum=0;
  52. // Which item is the largest
  53. $max_one=0 ;
  54. for ($start=$k;$start>0;$start--){
  55. // Find the maximum solution consisting of fixed $start elements
  56. $start_w_arr = getMaxCombination2($start);
  57. echo "Find Maximum solution consisting of $start elements: n";
  58. print_r($start_w_arr);
  59. echo "n";
  60. $sum=array_sum( $start_w_arr );
  61. // Note: Because it is arranged in descending order, $k- -, The earlier the combination $k with the same sum is found, the larger it is, that is, the better the solution, so it is less than not less than or equal to
  62. if($sum>$max_sum){
  63. $max_sum=$sum;
  64. $max_one=$k -$start;
  65. }
  66. $k_w_result[]= $start_w_arr ;
  67. }
  68. return $k_w_result[$max_one];
  69. }
  70. // Find a combination of the given $start elements in the array $rocks. These The sum of the elements is as large as possible but less than or equal to the specified value $w. The array has been sorted from large to small
  71. function getMaxCombination2($start) {
  72. //The rocks
  73. global $rocks;
  74. //The maximum number of rocks that the ship can load at a time Block
  75. global $k;
  76. // Maximum load capacity of the ship
  77. global $w;
  78. if(count($rocks)<$start){
  79. return array(0);
  80. }
  81. $c=count($rocks );
  82. // Generate a function based on $start, containing the $start layer for loop code, and then include it and call this function
  83. if(!file_exists( "$start.php")){
  84. $output_1="";
  85. $output_2='$sum=';
  86. $output_3='if($sum<=$w){ $arr=array(); ';
  87. $output_4='';
  88. for($i=0;$ i<$start;$i++){
  89. $output_1.='for($p'.$i.'='.$i.';$p'.$i.'<$c-'.($ start-$i-1).';$p'.$i.'++){'."n";
  90. if($i>0){
  91. $output_2.='+';
  92. }
  93. $ output_2.='$rocks[$p'.$i.']';
  94. $output_3.='$arr[]=$rocks[$p'.$i.'];';
  95. $output_4.=' }';
  96. }
  97. $output_2.=';';
  98. $output_3.=' return $arr; }' ;
  99. $output='';
  100. file_put_contents("$start.php",$output);
  101. include_once "$start.php";
  102. }
  103. else{
  104. include_once "$start.php";
  105. }
  106. return call_user_func('myfor'.$start ,$rocks,$c,$w);
  107. }
  108. //Start calculation
  109. //Array first Sorting from large to small, this operation is the key to saving time and effort in subsequent algorithms
  110. rsort($rocks);
  111. // In order to prevent the following algorithm from causing an infinite loop if the stone is too big and the boat is too small
  112. foreach ($rocks as $v){
  113. if($v>$w){
  114. die("It’s impossible to load the ship with stones. Let’s fight again with a bigger ship!" ");
  115. }
  116. }
  117. //Algorithm starts
  118. while(!empty($rocks)){
  119. // Start loading a ship
  120. $process[$count]=array();
  121. // Loading a ship
  122. $process[$count]= getMaxCombination( ) ;
  123. // Remove shipped
  124. from rocks foreach($process[$count] as $v){
  125. $key=array_search($v, $rocks) ;
  126. unset( $rocks[$key]);
  127. }
  128. $rocks=array_values($rocks);
  129. // Number of shipments + 1
  130. $count++;
  131. }
  132. // Output result
  133. echo 'Minimum times:' .$count."n";
  134. echo 'Shipping process:';
  135. print_r($process);
  136. ?>
Copy code
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
1 months ago By 尊渡假赌尊渡假赌尊渡假赌
Two Point Museum: All Exhibits And Where To Find Them
1 months ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Working with Flash Session Data in Laravel Working with Flash Session Data in Laravel Mar 12, 2025 pm 05:08 PM

Laravel simplifies handling temporary session data using its intuitive flash methods. This is perfect for displaying brief messages, alerts, or notifications within your application. Data persists only for the subsequent request by default: $request-

cURL in PHP: How to Use the PHP cURL Extension in REST APIs cURL in PHP: How to Use the PHP cURL Extension in REST APIs Mar 14, 2025 am 11:42 AM

The PHP Client URL (cURL) extension is a powerful tool for developers, enabling seamless interaction with remote servers and REST APIs. By leveraging libcurl, a well-respected multi-protocol file transfer library, PHP cURL facilitates efficient execution of various network protocols, including HTTP, HTTPS, and FTP. This extension offers granular control over HTTP requests, supports multiple concurrent operations, and provides built-in security features.

Simplified HTTP Response Mocking in Laravel Tests Simplified HTTP Response Mocking in Laravel Tests Mar 12, 2025 pm 05:09 PM

Laravel provides concise HTTP response simulation syntax, simplifying HTTP interaction testing. This approach significantly reduces code redundancy while making your test simulation more intuitive. The basic implementation provides a variety of response type shortcuts: use Illuminate\Support\Facades\Http; Http::fake([ 'google.com' => 'Hello World', 'github.com' => ['foo' => 'bar'], 'forge.laravel.com' =>

12 Best PHP Chat Scripts on CodeCanyon 12 Best PHP Chat Scripts on CodeCanyon Mar 13, 2025 pm 12:08 PM

Do you want to provide real-time, instant solutions to your customers' most pressing problems? Live chat lets you have real-time conversations with customers and resolve their problems instantly. It allows you to provide faster service to your custom

Explain the concept of late static binding in PHP. Explain the concept of late static binding in PHP. Mar 21, 2025 pm 01:33 PM

Article discusses late static binding (LSB) in PHP, introduced in PHP 5.3, allowing runtime resolution of static method calls for more flexible inheritance.Main issue: LSB vs. traditional polymorphism; LSB's practical applications and potential perfo

PHP Logging: Best Practices for PHP Log Analysis PHP Logging: Best Practices for PHP Log Analysis Mar 10, 2025 pm 02:32 PM

PHP logging is essential for monitoring and debugging web applications, as well as capturing critical events, errors, and runtime behavior. It provides valuable insights into system performance, helps identify issues, and supports faster troubleshoot

HTTP Method Verification in Laravel HTTP Method Verification in Laravel Mar 05, 2025 pm 04:14 PM

Laravel simplifies HTTP verb handling in incoming requests, streamlining diverse operation management within your applications. The method() and isMethod() methods efficiently identify and validate request types. This feature is crucial for building

Discover File Downloads in Laravel with Storage::download Discover File Downloads in Laravel with Storage::download Mar 06, 2025 am 02:22 AM

The Storage::download method of the Laravel framework provides a concise API for safely handling file downloads while managing abstractions of file storage. Here is an example of using Storage::download() in the example controller:

See all articles