PHP中的货物算法

Question

Honestly, i have a testing calculate how many containers of a given size and weight capacity it takes to pack the specified goods. But i'm really bad at algorithm, so i post this to looking some hint from you guys. Any help is appreciate. Thank you guys !

I have three container sizes and their capacities like this :

Container Size : Large
Maximum Volume (m3) : 76
Maximum Weight (kg) : 29,600

Container Size : Medium
Maximum Volume (m3) : 67.3 Maximum Weight (kg) : 27,397

Container Size : Small
Maximum Volume (m3) : 33 Maximum Weight (kg) : 22,100

Given a total weight and volume for goods in a shipment, the algorithm must output the most efficient combination of containers to pack the goods in. The system should use larger containers where possible, but empty space should be minimised.

For input of volume 213m3 and weight 22,421kg, the expected output is:

array(  
‘L’ => array(   
‘quantity’ => 2,   
‘volume’   => 152,   
‘weight’ => 16000  
),  
‘M’ => array(   
‘quantity’ => 1,   
‘volume’   => 61,   
‘weight’ => 6421  
),  
 ‘S’ => array(   
‘quantity’ => 0,   
‘volume’   => 0,   
‘weight’ => 0  
), 
) 

For input of volume 182m3 and weight 19,158kg, the expected output is:

array(  
‘L’ => array(   
‘quantity’ => 2,   
‘volume’   => 152,   
‘weight’ => 16000  
),  
‘M’ => array(   
‘quantity’ => 0,   
‘volume’   => 0,   
‘weight’ => 0  
),  
‘S’ => array(   
‘quantity’ => 1,   
‘volume’   => 30,   
‘weight’ => 3158  
), 
) 

I can't understand how it work ....

So please hint me.

Thank you.

Answer 1

The problem you are looking to solve is a well known NP-complete problem called as the knapsack problem. Here is the wikipedia link describing that problem :-

The best recommended way would be some sort of heuristics. Here's a paper that describes some useful heuristics to solve the knapsack problem.

Edit :- To explain a bit further, NP-complete problems are a known category of problems for which no efficient solution exists. i.e., there is no algorithm that is both fast and correct. Hence you have to use some kind of heuristic approximation algorithms to solve it that are both fast and reasonably correct.

What kind of heuristic would be best suited for your problem is probably out of the scope of stackoverflow. I've given you some resources and you can search more on this rather well studied problem.