How to divide items equally in 4 boxes? [closed]

Question

Suppose i have 7 bags with different weight. Actually a php array contains this data.

Bag A    60 Kg
Bag B    80 Kg
Bag C    20 Kg
Bag D    10 Kg
Bag E    80 Kg
Bag F    100 Kg
Bag G    90 Kg

In php it will look like this

    Array
(
    [30] => 60
    [31] => 120
    [32] => 120
    [33] => 60
    [35] => 180
)

Now i have to divide all 7 bags in 4 container equally by balancing there weight. But i cannot break the bag to manage weight. How to do this please suggest me. How can i build a formula or php function which will distribute all bags balancing there weight. There is no limitation in container capacity. And its also not necessary to have all containers weight equal after distribution. I just need a load balancing. Thanks in advance.

Answer 1

Create a function that gets a product weight and returns a bag number - the one which has the least free space that's still enough to fit. Put it in the bag. Repeat until done.

$bags = array(60,80,20,10,80,100,90);
$containers = array(1=>100,2=>100,3=>100,4=>100); // number -> free space
$placement = array();

rsort($bags); // biggest first - usually it's better

function bestContainerFor($weight) {
    global $containers;
    $rest = 0;
    $out = 0; // in it won't change $weight fits nowhere
    foreach($containers as $nr=>$space) {
        if($space<$weight) continue; // not enough space
        if($space-$weight<$rest) continue; // we have a better case
        $rest = $space-$weight;
        $out = $nr;
    }
    if($out) $containers[$out]-=$weight; // occupy the space
    return $out;
}

foreach($bags as $nr=>$w) {
    $p = bestContainerFor($w);
    $placement[$nr] = $p; // for later use; in this example it's not needed
    if( $p) print "Bag $nr fits in $p<br>";
    if(!$p) print "Bag $nr fits nowhere<br>";
}

It's not tested. If you give me some details of your code I'll try to adapt. This just shows the principle of it.

Note that

• it works with variable container sizes,
• it gives you the placement of each bag, not the sum weight,
• it's not optimal for equal distribution, just gives a good case

Answer 2

Calculate the sum of the weight of your bags then divide it by the number of containers. Then use a bin packaging algorithm to distribute the bags to the individual containers. E.g. take one bag at a time from your array and put it in the first container where the weight of the container plus the weight of your bag is less than the maximally possible container weight.

http://en.wikipedia.org/wiki/Bin_packing_problem

Update: example written in Ruby. Should be not to hard to rewrite it in PHP. It distributes the bags to the containers relatively evenly (There might be a solution that is more accurate).

# A list of bags with different weights
list_of_bags = [11, 41, 31, 15, 15, 66, 67, 34, 20, 42, 22, 25]
# total weight of all bags 
weight_of_bags = list_of_bags.inject(0) {|sum, i| sum + i}
# how many containers do we have at our disposal?
number_of_containers = 4
# How much should one container weight? 
weight_per_container = weight_of_bags / number_of_containers
# We make an array containing an empty array for each container
containers = Array.new(number_of_containers){ |i| [] }

# For each bag
list_of_bags.each do |bag| 
    # we try to find the first container 
    containers.each do |container| 
        # where the weight of the container plus the weigth of the bag is 
        # less than the maximum allowed (weight_per_container)
        if container.inject(0) {|sum, i| sum + i} + bag < weight_per_container
            # if the current container has space for it we add the bag
            # and go to the next one 
            container.push(bag)
            break
        end 
    end
end

# output all containers with the number of items and total weight
containers.each_with_index do |container, index| 
    puts "container #{index} has #{container.length} items and weigths: #{container.inject(0) {|sum, i| sum + i}}"
end

example result:

container 0 has 3 items and weigths: 83
container 1 has 3 items and weigths: 96
container 2 has 2 items and weigths: 87
container 3 has 2 items and weigths: 76