Logic Issue - how many / what small boxes in a big box - PHP / MySQL

Question

I have a problem and I will try to describe it as simple as possible conditions.

Using a combination of PHP and MySQL, I need to complete the following logical task: this is a simplified version of what is required, but in a nutshell the logic is the same.

Think of the boxes. I have many small boxes and one large box. I need to be able to fill a large box using a lot of small boxes.

So let's break it.

I have a table in MySQL that has the following lines

Table: small_boxes id | box_size ============= 1 | 100 2 | 150 3 | 200 4 | 1000 5 | 75 ..etc 

This table can work up to hundreds, and some fields are the same size

Now I have a requirement to fill one large box, for example, of size 800, with all the small_boxes combinations that I find in the table. A large box can be any size that the user wants to fill.

The goal here is inefficiency, for example, I don’t really need to bend a little or a little bit, just demonstrating various options for the boxes that can fit, within the allowable number.

Therefore, if possible, I would like to understand how to solve this problem in PHP / MySQL. I am competent enough in both, but the problem is how I approach this.

The examples would be fantastic, but I would gladly agree to a little information to get me started.

Answer 1

You should probably take a look at the glorious backpack problem.

Answer 2

https://codegolf.stackexchange.com/questions/3731/solve-the-knapsack-problem

Read about it.

Hope you take algebra 2 ..

Here are some PHP code to help you:

http://rosettacode.org/wiki/Knapsack_problem/0-1#PHP

Answer 3

Thanks to maxhd and Ugo Meda for pointing me in the right direction!

As a result, I came to something very close to what I needed. I'm not sure if this even gets into the "Backpack" problem, or depending on which one is changed, but here is the code I came up with. Feel free to criticize me!

To try and get a few different box options inside the backpack, I deleted the largest item on each iteration of the main loop, again, if there is a better way, let me know :)

Thanks!

 class knapsack { private $items; private $knapsack_size; private $tolerance = 15; //Todo : Need to make this better, perhaps a percentage of knapsack private $debug = 1; public function set_knapsack_size($size){ $this->knapsack_size = $size; } public function set_items($items){ if(!is_array($items)){ return false; } //Array in the format of id=>size, ordered by largest first $this->items = $items; } public function set_tolerance($tolerance){ $this->tolerance = $tolerance; } private function remove_large_items(){ //Loop through each of the items making sure we can use this sized item in the knapsack foreach($this->items as $list_id=>$list){ //Lets look ahead one, and make sure it isn't the last largest item, we will keep largest for oversize. if($list["size"] > $this->knapsack_size && (isset($this->items[$list_id+1]) && $this->items[$list_id+1]["size"] > $this->knapsack_size)){ unset($this->items[$list_id]); }else{ //If we ever get here, simply return true as we can start to move on return true; } } return true; } private function append_array($new_data,$array){ if(isset($array[$new_data["id"]])){ $array[$new_data["id"]]["qty"]++; }else{ $array[$new_data["id"]]["qty"] = 1; } return $array; } private function process_items(&$selected_items,$knapsack_current_size){ //Loop the list of items to see if we can fit it in the knapsack foreach($this->items as $list){ //If we can fit the item into the knapsack, lets add it to our selected_items, and move onto the next item if($list["size"] <= $knapsack_current_size){ $this->debug("Knapsack size is : ".$knapsack_current_size." - We will now take ".$list["size"]." from it"); $selected_items = $this->append_array($list,$selected_items); $knapsack_current_size -= $list["size"]; //Lets run this method again, start recursion $knapsack_current_size = $this->process_items($selected_items,$knapsack_current_size); }else{ //Lets check if we can fit a slightly bigger item into the knapsack, so we can eliminate really small items, within tolerance if(($list["size"] <= $knapsack_current_size + $this->tolerance) && $knapsack_current_size > 0){ $this->debug("TOLERANCE HIT : Knapsack size is : ".$knapsack_current_size." - We will now take ".$list["size"]." from it"); $selected_items = $this->append_array($list,$selected_items); $knapsack_current_size -= $list["size"]; } } //Lets see if we have to stop the recursion if($knapsack_current_size < 0){ return $knapsack_current_size; } } } private function debug($message=""){ if(!$this->debug){ return false; } echo $message."\n"; } public function run(){ //If any of the variables have not been set, return false if(!is_array($this->items) || !$this->knapsack_size){ return false; } //Lets first remove any items that may be too big for the knapsack $this->remove_large_items(); //Lets now check if we still have items in the array, just incase the knapsack is really small if(count($this->items) == 0){ return false; } //Now that we have a good items list, and we have no items larger than the knapsack, lets move on. $variants = array(); foreach($this->items as $list_id=>$list){ $this->debug(); $this->debug("Finding variants : "); $selected_items = array(); $this->process_items($selected_items,$this->knapsack_size); $variants[] = $selected_items; //Remove the largest variant, so we get a new set of unique results unset($this->items[$list_id]); } return $variants; } } $products = array( array("id"=>1,"size"=>90), array("id"=>2,"size"=>80), array("id"=>3,"size"=>78), array("id"=>4,"size"=>66), array("id"=>5,"size"=>50), array("id"=>6,"size"=>42), array("id"=>7,"size"=>36), array("id"=>8,"size"=>21), array("id"=>9,"size"=>19), array("id"=>10,"size"=>13), array("id"=>11,"size"=>7), array("id"=>12,"size"=>2), ); $knapsack = new knapsack(); $knapsack->set_items($products); $knapsack->set_knapsack_size(62); $result = $knapsack->run(); var_dump($result);