Example of Packing Algorithm Implemented by PHP

In this paper, the packing algorithm realized by PHP is described with examples. Share it for your reference, as follows:

Greedy method is a method that does not pursue the optimal solution, but only hopes to get a satisfactory solution. Greedy method 1 can get a satisfactory solution quickly, because it saves a lot of time that must be spent to find the optimal solution to exhaust all possibilities. The greedy method often makes the best choice based on the current situation, without considering all possible overall situations, so the greedy method does not go back.

For example, when shopping for change at ordinary times, in order to minimize the number of coins recovered, all kinds of publishing schemes for change are not considered, but the currencies with the largest face value are considered in descending order, and the currencies with large face value are used as much as possible first, and the currencies with smaller face value are considered only when the amount of the currencies with large face value is insufficient. This is using greed. This approach is always optimal here because of the banks' ingenious arrangement of the types and denominations of the coins they issue. If there are only coins with face values of 1, 5 and 11 units respectively, and you want to recover coins with a total value of 15 units. According to greedy algorithm, one coin with 11 unit face value and four coins with 1 unit face value should be found, and a total of five coins should be recovered. But the best solution should be three coins with a face value of 5 units.

[Problem] Packing problem

Problem description: The packing problem can be briefly described as follows: There are n articles with numbers 0, 1, …, n-1, and the volumes are v0, v1, …, vn-1 respectively. Put these n items into several boxes with the capacity of V. It is agreed that the volume of these n articles should not exceed V, that is, for 0 ≤ i < n, there is 0 < vi ≤ V. Different packing schemes may require different numbers of boxes. The packing problem requires that the number of boxes containing all n items should be less.

If the set of n items is divided into all subsets of n items or items less than n items, the optimal solution can be found. But the total of all possible divisions is too large. For an appropriately large n, the time it takes to find out all possible partitions is unbearable. Therefore, a very simple approximate algorithm, namely greedy method, is adopted for packing problem. The algorithm puts the items into the first box that it can put in in turn. Although the algorithm can't guarantee to find the optimal solution, it can still find a very good solution. Without losing generality, let the volumes of n items be arranged in order from large to small, that is, v 0 ≥ v 1 ≥ … ≥ vn-1. If the above requirements are not met, just sort the n items according to their volume from large to small, and then renumber the items according to the sorting results. The packing algorithm is simply described as follows:

{Enter the volume of the box;
Enter the number of items n;;
According to the order of volume from large to small, input the volume of each item;
Preset the used box chain to be empty;
Preset the used box counter box_count to 0;
for (i=0;i < n;i++)
{Searching for boxes j that can put articles i from the first used box;
if (no more articles can be put in used boxes i)
{Use another box and put the item i in this box;
box_count++;
}
else
Put the article i into the box j;;
}
}
The above algorithm can calculate the number of boxes box_count and the contents of each box. The following example shows that the algorithm can find the optimal solution without 1. There are 6 kinds of articles with volumes of 60, 45, 35, 20, 20 and 20 unit volumes, and the volume of boxes is 100 unit volumes. According to the above algorithm, 3 boxes are needed, and the items in each box are: the first box contains items 1 and 3; The second box contains articles 2, 4 and 5; The third box holds articles 6. The optimal solution is two boxes containing items 1, 4, 5 and 2, 3, 6 respectively.
If the items contained in each box are represented by a linked list, the pointer of the first node of the linked list is stored in a structure, which records the remaining space and the first pointer of the linked list of the items contained in the box. In addition, the information of all boxes also forms a linked list. The following is a program written according to the above algorithm.
}

Attached is an example of php:

<?php
// Articles 
$items[0] = 60;
$items[1] = 45;
$items[2] = 35;
$items[3] = 20;
$items[4] = 20;
$items[5] = 20;
$box_volume_count = 100; // Each box   Maximum volume of sub 
$box_count = 0; // Total number of shared boxes 
$item_count = count( $items );
$box = array();// Box   Subarray 
for ( $itemindex = 0; $itemindex < $item_count; $itemindex++ ) {
$_box_index = false;
$_box_count = count( $box );
for ( $box_index = 0; $box_index < $_box_count; $box_index++ ) {
 if ( $box[$box_index]['volume'] + $items[$itemindex] <= $box_volume_count ) {
 $_box_index = $box_index;
 break;
 }
}
if ( $_box_index === false ) {
 $box[$_box_count]['volume'] = $items[$itemindex];
 $box[$_box_count]['items'][] = $itemindex;
 $box_count++;
} else {
 $box[$_box_index]['volume'] += $items[$itemindex];
 $box[$_box_index]['items'][] = $itemindex;
}
}
print_r( $box );
?>

Run results:

Array
(
[0] = > Array
(
[volume] = > 95
[items] = > Array
(
[0] = > 0
[1] = > 2
)
)
[1] = > Array
(
[volume] = > 85
[items] = > Array
(
[0] = > 1
[1] = > 3
[2] = > 4
)
)
[2] = > Array
(
[volume] = > 20
[items] = > Array
(
[0] = > 5
)
)
)

For more readers interested in PHP related contents, please check the special topics of this site: "PHP Data Structure and Algorithm Tutorial", "php Programming Algorithm Summary", "php String (string) Usage Summary", "PHP Array (Array) Operation Skills Complete Book", "PHP Common Traversal Algorithms and Skills Summary" and "PHP Mathematical Operation Skills Summary"

I hope this paper is helpful to everyone's PHP programming.