Thread: How to combines differents pieces and form a package

> Sample of packages (boxes) finished
Box 4 seems overweight.

> the pieces come one each time and have 12 boxes (options) to distribute and form a packages.
So how many boxes can you fill concurrently ?

> Pieces can be discarded, when it's not possible fit at neither box.
Either means "a choice of two", so neither is "not a choice of two".

Do you have a finite number of items, and a finite number of boxes?
Say for example, 100 items need to be packed into 12 boxes, but you're only allowed to fill one box at once.

Why do you need to reject any?

If the current item doesn't fit in any box, just close the heaviest and start a fresh box.

Or are you saying that every full box must be in the narrow window of 2000 to 2030 grams.
30g seems an awfully small target to hit when the average random size is 10 times that.

What happens in extreme cases where every box is just over 1840g (say 250*4 + 300*2 + 240) and is incapable of storing any item of any size without going overweight.

Let's say you have 6 items in each of 12 boxes (72 in total). Can you use the distribution table?
I mean, if you haven't seen a 370g item in the last 72, chances would seem to be high that one might be along soon.
Or if you've seen two 370g items in the last 72, then you could pretty much discount the appearance of another one any time soon.
In other words, match the current distribution of all the items you currently know about with your long-term average to help with decision making.

Knapsack problem - Wikipedia
Bin packing problem - Wikipedia
Packing problems - Wikipedia

I'd say that the best way would be to weigh the packages ahead of time so that you could use Salem's suggested algorithms.

Going down a conveyor belt the order of the packages should remain constant, and you could slow down the speed so that you could look up to 100 packages ahead.

You could then determine if any packages won't fit in any boxes and reject them before packing (saving time and boxes). These could then be sent back through the weighing...

A sort of template for experimenting with.

Code:

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cstring>
#include <ctime>
#include <random>
using namespace std;

// Compile with g++ -std=c++11 foo.cpp

const int numBins = 12;
const int lowCapacity = 2000;
const int highCapacity = 2030;

void fillConveyorBelt(vector<int> &belt, int count = 1) {
    const int distribution[] = {
        2,7,19,34,24,7,3,2,2
    };
    const int baseWeight = 201;
    const int intervalWeight = 19;
    for ( int c = 0 ; c < count ; c++ ) {
        for ( size_t i = 0 ; i < sizeof(distribution)/sizeof(distribution[0]) ; i++ ) {
            int low = baseWeight + i * (intervalWeight+1);
            int high= low + intervalWeight;
            //cout << low << " " << high << " " << distribution[i] << endl;
            std::default_random_engine gen(time(NULL));
            std::uniform_int_distribution<int> dist(low,high);
            for ( int n = 0 ; n < distribution[i] ; n++ ) {
                belt.push_back(dist(gen));
            }
        }
    }
}

class bin {
    vector< vector<int> >   bins;
    vector<int>             capacity;
public:
    bin() :
        bins(numBins,vector<int>()),
        capacity(numBins,0)
        {
    }
    // add a piece to a bin, returning true if it was fitted.
    bool addPiece(int binNumber, int piece) {
        if ( checkPieceWillFit(binNumber,piece) ) {
            bins[binNumber].push_back(piece);
            capacity[binNumber] += piece;
            return true;
        } else {
            return false;
        }
    }
    // true if the piece will fit in a given bin
    bool checkPieceWillFit(int binNumber, int piece) {
        return capacity[binNumber] + piece <= highCapacity;
    }
    // true if the bin is optimally full
    bool binReadyForDispatch(int binNumber) {
        return capacity[binNumber] >= lowCapacity && capacity[binNumber] <= highCapacity;
    }
    // find the bin which is most empty
    int emptiestBin() {
        int empty = highCapacity;
        int id = 0;
        for ( int i = 0 ; i < numBins ; i++ ) {
            if ( capacity[i] < empty ) {
                empty = capacity[i];
                id = i;
            }
        }
        return id;
    }
    // Find the bin which is most full
    int fullestBin() {
        int full = 0;
        int id = 0;
        for ( int i = 0 ; i < numBins ; i++ ) {
            if ( capacity[i] > full ) {
                full = capacity[i];
                id = i;
            }
        }
        return id;
    }
    // The bin is judged to be full, so output the details and make it empty
    void dispatchBin(int binNumber) {
        cout << binNumber << "=" << capacity[binNumber] << ":";
        for ( size_t i = 0 ; i < bins[binNumber].size(); i++ ) {
            cout << bins[binNumber][i] << " ";
        }
        cout << endl;
        capacity[binNumber] = 0;
        bins[binNumber].resize(0);
    }
};

// Fill the bins in strict rotation
class linear : public bin {
    int     binNumber;
public:
    linear() :
        binNumber(0)
        {
    }
    void addPiece(int piece) {
        if ( bin::addPiece(binNumber,piece) ) {
            ;
        } else {
            // bin was full, empty it and add the piece
            dispatchBin(binNumber);
            bin::addPiece(binNumber,piece);
        }
        binNumber = (binNumber + 1) % numBins;
    }
};

// Best fit (bin with highest capacity)

// Worst fit (bin with lowest capacity)

// Probable fit (use cumulative histogram of all seen pieces to estimate the best bin)


int main ( ) {
    vector<int> belt;
    fillConveyorBelt(belt,100);
    shuffle(belt.begin(),belt.end(),std::default_random_engine(time(NULL)));
    cout << belt.size() << endl;
    linear  l;
    for ( int i = 0 ; i < 300 ; i++ ) {
        l.addPiece(belt[i]);
    }
}

Having filled the conveyor belt with thousands of items matching your distribution profile, you can experiment with pulling items off the belt one at a time and trying different strategies for filling the bins.