CODEWITHSUNDEEP
phpalgorithmmath
Ben
Ben

Reputation: 11188

Algorithm to find best combination of numbers - Bin Packing Prob lem

Say I have the following measures:

80 180 200 240 410 50 110

I can store each combination of numbers to a maximum of 480 per unit. How can I calculate the least number units required so all measures are spread in the most efficient way?

I've tagged PHP but it can be in JS too, or even pseudo language.

I know I'm supposed to tell what I did already but I'm quite stuck on how to approach this. The first thing that comes to mind is recursion but I'm no math expert to see how this can be done efficient...

Any help is greatly appreciated.

To further elaborate: I'm trying to calculate the number of skirtings I have to order, based on the different lengths I need for the walls. Each skirting has a length of 480cm and I want to know the best way to spread them so I have to buy the least number of skirtings. It's not so much about ordering a skirting extra, but the puzzle to figure it out is an interesting one (at least to me)

Update with solution

Despite people trying to close the question I've started fiddling with the Bin Packing Problem description and following the idea of sorting all items from largest to smallest and then fit them in the best possible way I created this small class that might help others in the future:

<?php
class BinPacker {
    private $binSize;

    public function __construct($binSize) {
        $this->binSize = $binSize;
    }

    public function pack($elements) {
        arsort($elements);
        $bins = [];
        $handled = [];

        while(count($handled) < count($elements)) {
            $bin = [];

            foreach($elements as $label => $size) {
                if(!in_array($label, $handled)) {
                    if(array_sum($bin) + $size < $this->binSize) {
                        $bin[$label] = $size;
                        $handled[] = $label;
                    }
                }
            }

            $bins[] = $bin;
        }

        return $bins;
    }

    public function getMeta($bins) {
        $meta = [
            'totalValue' => 0,
            'totalWaste' => 0,
            'totalBins' => count($bins),
            'efficiency' => 0,
            'valuePerBin' => [],
            'wastePerBin' => []
        ];

        foreach($bins as $bin) {
            $value = array_sum($bin);
            $binWaste = $this->binSize - $value;

            $meta['totalValue'] += $value;
            $meta['totalWaste'] += $binWaste;
            $meta['wastePerBin'][] = $binWaste;
            $meta['valuePerBin'][] = $value;

        }

        $meta['efficiency'] = round((1 - $meta['totalWaste'] / $meta['totalValue']) * 100, 3);

        return $meta;
    }
}

$test = [
    'Wall A' => 420,
    'Wall B' => 120,
    'Wall C' => 80,
    'Wall D' => 114,
    'Wall E' => 375,
    'Wall F' => 90
];

$binPacker = new BinPacker(488);
$bins = $binPacker->pack($test);

echo '<h2>Meta:</h2>';
var_dump($binPacker->getMeta($bins));

echo '<h2>Bin Configuration</h2>';
var_dump($bins);

Which gives an output:

Meta:

array (size=6)
  'totalValue' => int 1199
  'totalWaste' => int 265
  'totalBins' => int 3
  'efficiency' => float 77.898
  'valuePerBin' => 
    array (size=3)
      0 => int 420
      1 => int 465
      2 => int 314
  'wastePerBin' => 
    array (size=3)
      0 => int 68
      1 => int 23
      2 => int 174

Bin Configuration

array (size=3)
  0 => 
    array (size=1)
      'Wall A' => int 420
  1 => 
    array (size=2)
      'Wall E' => int 375
      'Wall F' => int 90
  2 => 
    array (size=3)
      'Wall B' => int 120
      'Wall D' => int 114
      'Wall C' => int 80

While the data set is relatively small a rather high inefficiency rate is met. But in my own configuration where I entered all wall and ceiling measures I've reached an efficiency of 94.212% (n=129 measures).

(Note: the class does not check for ambigious labels, so if for example you define Wall A twice the result will be incorrect.)

Conclusion: for both the ceiling and the wall skirtings I can order one less skirting than my manual attempt to spread them efficiently.

Upvotes: 0

Views: 953

Answers (1)

S. Kelly
S. Kelly

Reputation: 155

Looks to me like a variation on the Bin Packing Problem where you're trying to pick the combination of elements that make up 480 (or just under). This is a fairly computationally hard problem and depending on how efficient/accurate it needs to be, might be overkill trying to get it exact.

A rough heuristic could be just to sort the measures, keep adding the smallest ones into a unit until the next one makes you go over, then add to a new unit and repeat.

Upvotes: 2

Related Questions