php solves boxing problem-PHP Tutorial-php.cn

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
)

)

// PHP exercise boxing problem
// author: mx (http://my.oschina.net/meikaiyuan)
// 2013/5/30
// Question:
// http://www.oschina.net/question/117304_112681
/*
Title:
I have asked similar questions before, but there is no good answer. So I want to ask again.
There is a pile of large and small stones that need to be pulled to the other side of the river by boat
--There are m pieces of stone, and the weight of each piece is known
--The boat can only load k stones at a time, and the loading weight cannot exceed w
--I want to find out the minimum number of trips that can transport all the stones across the river.
------------------------------------
Example 1
There are 9 stones, their weights are 1,2,3,4,5,6,7,8,9
k=3
w=15
The result is that it can be shipped in at least 3 times.
------------------------------------
Example 2
There are 9 stones, each weighing 1 ,1,1,5,6,6,7,9,9
k=3
w=15
The result is that it takes at least 4 times to complete the shipment.
*/
//Code starts
//Stones
global $rocks;
//The maximum number of pieces the ship can load at a time
global $k;
//The maximum load capacity of the ship
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); //Change to this set of data and try the result?
$w=15;
//How many times has it been shipped currently?
$count=0;
//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?
$process=array();
// 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
function getMaxCombination( ) {
//Stones
global $rocks;
//How many pieces can the ship carry at most? global $k;
//The maximum load capacity of the ship
global $w;
/ / Save the largest set under various $k that the sum of all elements is less than or equal to w and is the largest
$k_w_result=array();
// Maximum combination value
$max_sum=0;
// Which item is the largest
$max_one=0 ;
for ($start=$k;$start>0;$start--){
// Find the maximum solution consisting of fixed $start elements
$start_w_arr = getMaxCombination2($start);
echo "Find Maximum solution consisting of $start elements: n";
print_r($start_w_arr);
echo "n";
$sum=array_sum( $start_w_arr );
// 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
if($sum>$max_sum){
$max_sum=$sum;
$max_one=$k -$start;
}
$k_w_result[]= $start_w_arr ;
}
return $k_w_result[$max_one];
}
// 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
function getMaxCombination2($start) {
//The rocks
global $rocks;
//The maximum number of rocks that the ship can load at a time Block
global $k;
// Maximum load capacity of the ship
global $w;
if(count($rocks)<$start){
return array(0);
}
$c=count($rocks );
// Generate a function based on $start, containing the $start layer for loop code, and then include it and call this function
if(!file_exists( "$start.php")){
$output_1="";
$output_2='$sum=';
$output_3='if($sum<=$w){ $arr=array(); ';
$output_4='';
for($i=0;$ i<$start;$i++){
$output_1.='for($p'.$i.'='.$i.';$p'.$i.'<$c-'.($ start-$i-1).';$p'.$i.'++){'."n";
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);
}
//Start calculation
//Array first Sorting from large to small, this operation is the key to saving time and effort in subsequent algorithms
rsort($rocks);
// In order to prevent the following algorithm from causing an infinite loop if the stone is too big and the boat is too small
foreach ($rocks as $v){
if($v>$w){
die("It’s impossible to load the ship with stones. Let’s fight again with a bigger ship!" ");
}
}
//Algorithm starts
while(!empty($rocks)){
// Start loading a ship
$process[$count]=array();
// Loading a ship
$process[$count]= getMaxCombination( ) ;
// Remove shipped
from rocks foreach($process[$count] as $v){
$key=array_search($v, $rocks) ;
unset( $rocks[$key]);
}
$rocks=array_values($rocks);
// Number of shipments + 1
$count++;
}
// Output result
echo 'Minimum times:' .$count."n";
echo 'Shipping process:';
print_r($process);
?>

Copy code

Php8, I'm coming too

Learn website layout in 30 minutes

Shangguan Oracle Beginner to Proficient Video Tutorial

Your first line of UNI-APP code

Flutter from scratch to app launch

Brother Lian New Linux Video Tutorial

AXURE 9 Video Tutorial (Suitable for Product Manager Interactive Product Design UI)

Zero Basic Proficiency PS Video Tutorial

16 day UI video tutorial to get you started

PS Techniques and Slicing Techniques Video Tutorial

Alibaba Cloud Environment Construction and Project Launch Video Tutorial

Overview of Computer Networks - Basic Knowledge that Programmers Must Master

Essential Tutorial for Programmers - HTTP Protocol Explanation

Websocket Video Tutorial

php solves boxing problem