# Thread: How to combines differents pieces and form a package

1. ## How to combines differents pieces and form a package

Hi friends!

I need find a best way to combine pieces with 200-380g weight and form a package (box) of 2000 - 2030 grams.

At the system, the pieces come one each time and have 12 boxes (options) to distribute and form a packages.

Pieces can be discarded, when it's not possible fit at neither box.
But the Rejects needs be low.

Someone Knows a Algorithm to help me a resolve this situation ?

collected statistics of pieces occurrences Sample of packages (boxes) finished  2. > 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. 3. Originally Posted by Salem > Sample of packages (boxes) finished
Box 4 seems overweight.
Yes, Sorry.... It's only a manual sample with error

> 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 ?
12 boxes at same time, when one box complete 2000g, the user press a button to reset and start again

> 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".
160 pices by minute comes, 8% of reject (discarded pieces is acceptable), these pieces go to 13 box.

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.
No, no order, all itens can be distributed at any box in any time or order 4. This software run in this machine:

Actually, I have a software working at other situations, but 200-380g with 270g average pieces, is a difficult case! 5. 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 6. I did not express myself because of my short English.

* Yes, all packages need be to 2000 - 2030 grams, reject is a option to discard pieces when no way to fit the package, even in cases not last piece on package.

* Yes, 1840g block any chance to fit a package 2000-2030, the routine prevent this (rejecting pieces).

* Current routine have a table with last n pieces and know how the most common pieces. (77% between 240g-300g)
With only one low limit piece (200-240) or high limite piece (300-360) for each 6 pieces, is very difficult fit a package.
The routine needs to select the middle parts well.

For now, I'll also study these algorithms.... Thanks! 7. Apparently these algorithms serve to solve the same problem, but when we already know all the pieces available ...

Which is not exacly my case. 8. 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... 9. 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) ; 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
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)
{
}
;
} else {
// bin was full, empty it and add the piece
dispatchBin(binNumber);
}
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++ ) {
}
}```
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. 10. Thanks you so much SALEM,

Now I'm studying your code, as soon as possible I will comment about results.... Popular pages Recent additions box, boxes, form, package, pieces 