Continuing with the vector

[eduard77]

Thank you for your help so far.I try now to move on with my vector but now comes the hardest part.
All the values that the float vector receives must combine somehow that the value of their addition do not overcome 12.
So in other words even if I have 100 entries the program must find the best combination from all sum of the values that are closest to 12.
ex. 2.65, 4.56, 8.98, 5.21 etc
So the program must find that 2.65 + 4.56 + 5.21 is the closest to 12.
Thank you

[ravenous]

How do you define the "best" combination?

I think that this could be quite hard, sine there are a huge number of combinations in which the numbers can be summed. For a general case you can't know how many of the numbers you will have to use (they could all be very small, or one of them could just be 12, so you'd only need one number). Anyway, in the general case the possible number of ways to sum from 1 to 100 numbers is:

[tex]
\begin{align}
N &= 2\sum^{50}_{r = 1}{{100}\choose{r}}\\
&= 2\left({{100}\choose{1}} + {{100}\choose{2}} + {{100}\choose{3}} + {{100}\choose{4}} + \ldots + {{100}\choose{49}} + {{100}\choose{50}}\right)\\
&= 2(100 + 4950 + 161700 + 3921225 + \ldots + 9.89\times 10^{28} + 1.01\times 10^{29})
\end{align}
[/tex]

This number is going to be of the order > 1E+30 possible combinations, so exhaustively finding any particular combination is not possible.

[eduard77]

So, any idea for a more empiric approach?

[eduard77]

What about grouping them in categories?
let's say category 1; bars that are less than 1m en we need at least 12 of them
category 2: bar that are until 1.5 m and we need at least 12 ofthem
category 3: bars that have between 1.5 and 2 m : and so one
What do you say?

[ravenous]

What about grouping them in categories?
let's say category 1; bars that are less than 1m en we need at least 12 of them
category 2: bar that are until 1.5 m and we need at least 12 ofthem
category 3: bars that have between 1.5 and 2 m : and so one
What do you say?

What about my original question: How are you deciding which is the "best" combination?

[arkoenig]

If by "best" you mean the closest to 12 without being greater than 12, then what you have just described is a version of the knapsack problem, which is known to be hard to solve efficiently.

[ravenous]

If by "best" you mean the closest to 12 without being greater than 12, ...

I was wondering if the "best" might involve using the fewest elements, or the most consecutive (or at least closest together) elements or the smallest variance between elements or something of that nature?

[eduard77]

It doesn't really matter. They are iron bars. As long as I find the first combination that gives me the less waste I start cutting. let's say that I found 2.36+2.43+2.89+2.98+1.2 . I just have to look that if I have something that matches with to 0.14 and if I find I put it. And after that I start cutting let's say 89 pieces of 2.36 m and the difference of the others until I finish with the 89 pieces and after that I move the the next best combination.

[ravenous]

Hmmm... in that case, I guess the problem is different to what I thought, since what you're trying to do is use all the elements in the vector. Right?

In this case, I think a reasonably robust algorithm might be similar to the one that I generally use for putting things in boxes. I usually approach this by putting the biggest things in first, with the idea that the smaller ones can fit in the gaps more easily. Is there a limit on the number of 12m bars that you have to get the bits out of? To translate this into your problem (assuming that the number of bars is not known), I guess I'd do something like this:

1. Get the lengths into a std::vector
2. Use std::sort to sort the lengths
3. Remove the biggest piece first and add it to another vector that stores the details of the cuts from each bar
4. Do the same for the next biggest piece that you can get from the remaining bit of bar
5. Keep doing this until the bar is used
6. Start cutting a new bar and do the same thing
7. Keep doing this until all the pieces are used

This Kind of greedy algorithm should work OK, provided you have a sufficient number of small pieces to cut. If not, then another algorithm would be required.

[eduard77]

Eventually I made it like this because I think that is easier for me to work with.

#include <iostream>
#include <vector>
using namespace std;

typedef vector<double>BARE;

int main () {

	BARE categ1;
	BARE categ2;
	BARE categ3;
	BARE categ4;
	BARE categ5;
	BARE categ6;
	BARE categ7;
	BARE categ8;


	double x;
	int num;
	cout<<" Insert the number of measures: ";
	cin>>num;
	cout<< "Insert x: ";

	for( int i=0; i<num; i++) {
		cin>>x;
	  if (x>0 && x<=1)
		  categ1.push_back(x);
	  if( x>1 && x<=1.5)
		  categ2.push_back(x);
	  if (x>1.5 && x<=2)
		  categ3.push_back(x);
	  if (x>2 && x<=2.5)
		  categ4.push_back(x);
	  if (x>2.5 && x<=3)
		  categ5.push_back(x);
	  if (x>3 && x<=4)
		  categ6.push_back(x);
	  if (x>4 && x<=6)
		  categ7.push_back(x);
	  if (x>6 && x<=12)
		  categ3.push_back(x);
	 // for( int j = 0; j < categ1.size(); j++ ) 
		//cout << categ1[j] << endl; 
	 // for( int z = 0; z < categ2.size(); j++ ) 
		//	cout << categ2[z] << endl; 
	}
	system("pause");
	return 0;
	
}

I am a beginner I think that is better to find the biggest value and then just looking in the other categories to find the appropriate values.
So please let me know what you think about it so I can move on.
Thank you

[ravenous]

I'm still not sure what the point of categorising the lengths is? I think that it ends up being a kind of less efficient sort. If you need to sort a vector it is very easy, using std::sort , so you could do something like:

/* Get number of cuts from user */
#include <iostream>
#include <vector>
#include <algorithm>    // contains sort() and copy()
#include <iterator>     // contains ostream_iterator()

int main(){
    unsigned n;
    std::cout << "Enter the number of lengths to cut: ";
    std::cin >> n;

    /* Put the desired lengths in to a std::vector */
    std::vector< double > lengths(n);
    for(unsigned i = 0; i < n; ++i){
        std::cout << "Length " << i + 1 << " = ";
        double temp;
        std::cin >> temp;
        
        /* Check that the length seems sensible */
        if((temp <= 0) || (temp > 12)){
            std::cerr << "Error, length should be in the range (0,12]" << std::endl;
            --i;
        }
        else
            lengths[i] = temp;
    }

    /* Output the original vector */
    std::cout << "Original vector:" << std::endl;
    std::copy(lengths.begin(), lengths.end(), std::ostream_iterator< double >(std::cout, " "));

    /* Sort the vector into ascending order*/
    std::sort(lengths.begin(), lengths.end());

    /* Output the sorted vector */
    std::cout << "Sorted vector:" << std::endl;
    std::copy(lengths.begin(), lengths.end(), std::ostream_iterator< double >(std::cout, " "));

    return 0;
}

All the sorting is done in one line, on line 33. From this point you just have to go to the end of lengths and get the biggest bar, put this in a new bar, erase it, look through the rest of lengths until you find a piece smaller than the remaining length of the current bar, etc.

[eduard77]

The problem that I cannot solve yet is that I have to associate each lenght with a number of bars.
For example I need 86 bars of 1.56 m, 25 bars of 5.36m and so on, so I have to associate the lengths with the number of bars.
That's what I thought that if I put them in order in different vectors I might associate them easier.
What do you think?

[ravenous]

I don't think that it makes any difference to the computer. If I had 86 of 1.56, 23 of 5.36 and 9 of 0.45, I'd just do something like:

std::vector< double > lengths;
for(unsigned i = 0; i < 86; ++i)
    lengths.push_back(1.56);

for(unsigned i = 0; i < 23; ++i)
    lengths.push_back(5.36);

for(unsigned i = 0; i < 9; ++i)
    lengths.push_back(0.45);

and then do the sorting as normal, the result will be the same as if you'd used some kind of more complex procedure involving recording the number of each length explicitly. The only downside might be if the numbers of pieces are really high, then the sorting might take a little longer. This shouldn't be a problem unless someone wants 200,000 of one length and 300,000 of another, or something! The main difference is how you ask the user for the data.

[eduard77]

Sorry but I don't understand.
The problem is like this:
I have n dimensions and m categories.
Each dimension has to be associated with a category.
Both of the are inputs from the users.
To understand better the problem is this.
In construction you have to cut the 12 m standard iron bars in pieces of different lengths. The number of lengths and the dimensions are given by the engineer and I have to cut them like I have the less waste possibly(because the iron is expensive).
So that's why I just cannot figure it out how to associate them .

[ravenous]

OK, so the request from the engineer comes as:
"I'd like the following lengths:
10 x 1.32m,
24 x 2.43m,
17 x 0.23m,
9 x 4.54m"

If I were you, I'd store the information about each cut as a structure. You can read more about structures here. You could have something like:

struct Cut{
    unsigned number;
    double length;
};

You can then create a vector of these in your program, and put the requested sizes and numbers into it. I've put the way that I would do this below. Have a look at it, if you haven't seen some of the things before, you should be able to google them quite easily using something like "C++ vector iterator", for example.

/* Make a vector to store all the cuts in */
std::vector< Cut > allCuts;
Cut currentCut;

/* Get the number of different lengths from the user */
unsigned numberOfSizes;
std::cout << "Enter number of different sizes: ";
std::cin >> numberOfSizes;

/* Now get the actual numbers and lengths from the user */
for(unsigned i = 0; i < numberOfSizes; ++i){
    std::cout << "Enter new cut: <number> <length>" << std::endl;
    std::cin >> currentCut.number >> currentCut.length;
    /* Check that the length is sensible */
    if((currentCut.length <= 0) || (currentCut.length > 12)){
        std::cerr << "Error length must be in the range (0,12]" << std::endl;
        --i;
    }
    else
        allCuts.push_back(currentCut);
}

/* Now put all the cuts into a single large vector */
std::vector< double > lengths;
for(unsigned i = 0; i < allCuts.size(); ++i){
    for(unsigned j = 0; j < allCuts[i].number; ++j)
        lengths.push_back(allCuts[i].length);
}

/* Sort the vector */
std::sort(lengths.begin(), lengths.end());

/* Make a place to put the lengths to cut from each bar */
const unsigned NEW_BAR_LENGTH = 12;
std::vector< std::vector< double > > bars;
std::vector< double > currentBar;
double remainingLength = NEW_BAR_LENGTH;

/* Now keep going through the lengths vector until all the cuts are accounted for */
while(lengths.size() > 0){
    /* start at the longest length that needs to be cut ... */
    std::vector< double >::iterator it = lengths.end() - 1;
    /* Go until the smallest length that's needed is reached */
    while(it >= lengths.begin()){
        /* Check if the current length will fit */
        if(*it < remainingLength){ /* If it will... */
            /* ... Add it to the current bar and remove it from the list to be fitted */
            currentBar.push_back(*it);
            /* Update the amount of the bar remaining */
            remainingLength -= *it;
            /* Remove the current element from the lengths vector */
            l.erase(it);
        }
        /* Check that we didn't just remove the last element */
        if(l.size() > 0){
            /* length[0] is the shortest length cut that we still need to get
               if this is more than the remaining amount of the current bar,
               then we should finish this bar and start a new one, check for
               this now */
            if(lengths[0] > remainingLength){
                /* Reset the remaining length */
                remainingLength = NEW_BAR_LENGTH;
                /* Add this completed bar to the vector of bars */
                bars.push_back(currentBar);
                /* Clear the current bar */
                currentBar.clear();
                /* Exit this loop and start on the new bar */
                break;
            }
        }
        --it;
    }
}

I have used iterators to manipulate the vector in the while() loop starting on line 40. If you have never used iterators, you can read more about them here. Basically, they're a bit like pointers for STL containers (such as std::vector ).
You can then print out the result by doing something like:

double totalWaste = 0.0;
for(unsigned i = 0; i < bars.size(); ++i){
    std::cout << "Bar " << std::setw(2) << i + 1 << ":\t";
    for(unsigned j = 0; j < bars[i].size(); ++j)
        std::cout << std::setprecision(3) << std::fixed << bars[i][j] << " ";
    std::cout << std::endl;
    std::partial_sum(bars[i].begin(), bars[i].end(), bars[i].begin());
    totalWaste += NEW_BAR_LENGTH - bars[i].back();
}

/* Print a summary */
std::cout << "===============================" << std::endl;
std::cout << "Bars used:\t" << bars.size() << std::endl;
std::cout << "Total waste:\t" << totalWaste << " m" << std::endl;
std::cout << "Waste/Bar:\t" << totalWaste/bars.size() << " m" << std::endl;
std::cout << "===============================" << std::endl;

I have used the following header files for this example:

#include <iostream>
#include <iomanip>
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>

The output on my machine looks something like this:

Bar  1:	5.994 5.837 0.120 
Bar  2:	5.824 5.739 0.419 
Bar  3:	5.713 5.696 0.516 
Bar  4:	5.591 5.585 0.823 
Bar  5:	5.544 5.514 0.940 
Bar  6:	5.497 5.470 0.996 
Bar  7:	5.466 5.413 0.850 0.236 
Bar  8:	5.360 5.349 1.185 0.098 
Bar  9:	5.341 5.280 1.374 
Bar 10:	5.152 5.106 1.706 
Bar 11:	5.041 5.035 1.776 
Bar 12:	4.975 4.889 2.124 
Bar 13:	4.846 4.825 2.251 
Bar 14:	4.791 4.699 2.406 
Bar 15:	4.628 4.619 2.746 
Bar 16:	4.609 4.561 2.641 
Bar 17:	4.431 4.326 3.239 
Bar 18:	4.304 4.127 3.532 
Bar 19:	4.120 4.105 3.773 
Bar 20:	4.006 3.979 3.944 
Bar 21:	3.840 3.825 3.814 0.385 
Bar 22:	3.676 3.642 3.324 1.310 
Bar 23:	3.190 3.160 3.156 2.401 
Bar 24:	3.146 3.080 3.078 2.637 
Bar 25:	3.075 2.961 2.864 2.626 0.379 
Bar 26:	2.391 2.366 2.189 2.115 2.102 0.779 
Bar 27:	2.093 2.011 1.982 1.755 1.700 1.667 0.653 
===============================
Bars used:	27
Total waste:	1.545 m
Waste/Bar:	0.057 m
===============================

Hope that helps a little. If it all seems a bit confusing, read through the code carefully and google for terms/functions that you have never seen before.

Finally, on a practical note, you should add the width of the saw used to cut the bars to each length too. I don't know what this is for you, but I'm sure you can add it in OK :)

[eduard77]

Thank you.
I have to go to work now and I will study there what you wrote.

[eduard77]

I tried to compile your code but It gives me error.

#include <iostream>
#include <iomanip>
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>
/* Get the number of different lengths from the user */
struct Cut{
    unsigned number;
	double length;
};
std::vector< Cut > allCuts;
Cut* currentCut;


int main () {
unsigned numberOfSizes;
std::cout << "Enter number of different sizes: ";
std::cin >> numberOfSizes;
 
/* Now get the actual numbers and lengths from the user */
for(unsigned i = 0; i < numberOfSizes; ++i){
    std::cout << "Enter new cut: <number> <length>" << std::endl;
    std::cin >> currentCut.number >> currentCut.length;
    /* Check that the length is sensible */
    if((currentCut.length <= 0) || (currentCut.length > 12)){
        std::cerr << "Error length must be in the range (0,12]" << std::endl;
        --i;
    }
    else
        allCuts.push_back(currentCut);
}
 
/* Now put all the cuts into a single large vector */
std::vector< double > lengths;
for(unsigned i = 0; i < allCuts.size(); ++i){
    for(unsigned j = 0; j < allCuts[i].number; ++j)
        lengths.push_back(allCuts[i].length);
}
 
/* Sort the vector */
std::sort(lengths.begin(), lengths.end());
 
/* Make a place to put the lengths to cut from each bar */
const unsigned NEW_BAR_LENGTH = 12;
std::vector< std::vector< double > > bars;
std::vector< double > currentBar;
double remainingLength = NEW_BAR_LENGTH;
 
/* Now keep going through the lengths vector until all the cuts are accounted for */
while(lengths.size() > 0){
    /* start at the longest length that needs to be cut ... */
    std::vector< double >::iterator it = lengths.end() - 1;
    /* Go until the smallest length that's needed is reached */
    while(it >= lengths.begin()){
        /* Check if the current length will fit */
        if(*it < remainingLength){ /* If it will... */
            /* ... Add it to the current bar and remove it from the list to be fitted */
            currentBar.push_back(*it);
            /* Update the amount of the bar remaining */
            remainingLength -= *it;
            /* Remove the current element from the lengths vector */
            l.erase(it);
        }
        /* Check that we didn't just remove the last element */
        if(l.size() > 0){
            /* length[0] is the shortest length cut that we still need to get
               if this is more than the remaining amount of the current bar,
               then we should finish this bar and start a new one, check for
               this now */
            if(lengths[0] > remainingLength){
                /* Reset the remaining length */
                remainingLength = NEW_BAR_LENGTH;
                /* Add this completed bar to the vector of bars */
                bars.push_back(currentBar);
                /* Clear the current bar */
                currentBar.clear();
                /* Exit this loop and start on the new bar */
                break;
            }
        }
        --it;
    }
}

double totalWaste = 0.0;
for(unsigned i = 0; i < bars.size(); ++i){
    std::cout << "Bar " << std::setw(2) << i + 1 << ":\t";
    for(unsigned j = 0; j < bars[i].size(); ++j)
        std::cout << std::setprecision(3) << std::fixed << bars[i][j] << " ";
    std::cout << std::endl;
    std::partial_sum(bars[i].begin(), bars[i].end(), bars[i].begin());
    totalWaste += NEW_BAR_LENGTH - bars[i].back();
}
 
/* Print a summary */
std::cout << "===============================" << std::endl;
std::cout << "Bars used:\t" << bars.size() << std::endl;
std::cout << "Total waste:\t" << totalWaste << " m" << std::endl;
std::cout << "Waste/Bar:\t" << totalWaste/bars.size() << " m" << std::endl;
std::cout << "===============================" << std::endl;
return 0;
}

[ravenous]

And that error is... ?

[eduard77]

The error is only here

std::cout << "Enter new cut: <number> <length>" << std::endl;
    std::cin >> currentCut.number >> currentCut.length;
    /* Check that the length is sensible */
    if((currentCut.length <= 0) || (currentCut.length > 12)){
        std::cerr << "Error length must be in the range (0,12]" << std::endl;
        --i;

.number' must have class/struct/union
.length' must have class/struct/union
error C2664: 'void std::vector<_Ty>::push_back(_Ty &&)' : cannot convert parameter 1 from 'Cut *' to 'Cut &&'

[ravenous]

This generally means that you're using the 'dot' ( . ) operator when you should be using the 'pointer-to-member' ( -> ) operator. In this case, it is because you have defined currentCut as a pointer to a Cut structure (on line 15) and you haven't actually made a Cut for it to point at. There's not really any need to do this here, you can just declare currentCut normally, using Cut currentCut . If Cut was a very large structure, containing many, many members then maybe it would be a good idea. In that case, you'd have to declare it as:

/* Make a pointer to a Cut structure */
Cut *currentCut;

/* Point it at a piece of memory big enough to hold a Cut structure */
currentCut = new Cut;

/* Use the pointer to access the members */
currentCut->length = 1.52;

Also, you have declared currentCut and allCuts as global variables (outside of main() ), there's hardly ever a need to do this, and there definitely isn't a need to do it here.

[eduard77]

I did that but the next error is
error C2065: 'l' : undeclared identifier

[ravenous]

I did that but the next error is
error C2065: 'l' : undeclared identifier

That means that a variable called l has been used in the code, but not declared anywhere. (actually, this is kind of my fault, since I originally wrote the program with a vector called l but then I changed it to lengths when I posted it, to make it a bit clearer :) ). Search for l in the the code and replace it with lengths .

In general, you get this error as a result of typos, changing names of things retrospectively or something like that.

[eduard77]

Now the code is compiling well but I introduced the data like:
1. Enter number of different sizes: 2
2. Enter new cut <number>< length >
6 2.63 3 6.91
==========================
Bars used 0
Total waste 0 m
Waste /Bar: -1. IND m
==========================
All the data I enter I receive the same result

[eduard77]

sorry I forgot the code

#include <iostream>
#include <iomanip>
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>
/* Get the number of different lengths from the user */
struct Cut{
    unsigned number;
	double length;
};
std::vector< Cut > allCuts;
Cut *currentCut;


int main () {
unsigned numberOfSizes;
std::cout << "Enter number of different sizes: ";
std::cin >> numberOfSizes;
 
/* Now get the actual numbers and lengths from the user */
for(unsigned i = 0; i < numberOfSizes; ++i){
	currentCut = new Cut;
    std::cout << "Enter new cut: <number> <length>" << std::endl;
	std::cin >> currentCut ->number >> currentCut->length;
    /* Check that the length is sensible */
    /*if((currentCut->length <= 0) || (currentCut->length > 12)){
        std::cerr << "Error length must be in the range (0,12]" << std::endl;
        --i;
    }
    else
        allCuts.push_back(currentCut);
}*/
 
/* Now put all the cuts into a single large vector */
std::vector< double > lengths;
for(unsigned i = 0; i < allCuts.size(); ++i){
    for(unsigned j = 0; j < allCuts[i].number; ++j)
        lengths.push_back(allCuts[i].length);
}
 
/* Sort the vector */
std::sort(lengths.begin(), lengths.end());
 
/* Make a place to put the lengths to cut from each bar */
const unsigned NEW_BAR_LENGTH = 12;
std::vector< std::vector< double > >bars;
std::vector< double > currentBar;
double remainingLength = NEW_BAR_LENGTH;
 
/* Now keep going through the lengths vector until all the cuts are accounted for */
while(lengths.size() > 0){
    /* start at the longest length that needs to be cut ... */
    std::vector< double >::iterator it = lengths.end() - 1;
    /* Go until the smallest length that's needed is reached */
    while(it >= lengths.begin()){
        /* Check if the current length will fit */
        if(*it < remainingLength){ /* If it will... */
            /* ... Add it to the current bar and remove it from the list to be fitted */
            currentBar.push_back(*it);
            /* Update the amount of the bar remaining */
            remainingLength -= *it;
            /* Remove the current element from the lengths vector */
           lengths.erase(it);
        }
        /* Check that we didn't just remove the last element */
        if(lengths.size() > 0){
            /* length[0] is the shortest length cut that we still need to get
               if this is more than the remaining amount of the current bar,
               then we should finish this bar and start a new one, check for
               this now */
            if(lengths[0] > remainingLength){
                /* Reset the remaining length */
                remainingLength = NEW_BAR_LENGTH;
                /* Add this completed bar to the vector of bars */
                bars.push_back(currentBar);
                /* Clear the current bar */
                currentBar.clear();
                /* Exit this loop and start on the new bar */
                break;
            }
        }
        --it;
    }
}

double totalWaste = 0.0;
for(unsigned i = 0; i < bars.size(); ++i){
    std::cout << "Bar " << std::setw(2) << i + 1 << ":\t";
    for(unsigned j = 0; j < bars[i].size(); ++j)
        std::cout << std::setprecision(3) << std::fixed << bars[i][j] << " ";
    std::cout << std::endl;
    std::partial_sum(bars[i].begin(), bars[i].end(), bars[i].begin());
    totalWaste += NEW_BAR_LENGTH - bars[i].back();
}
 
/* Print a summary */
std::cout << "===============================" << std::endl;
std::cout << "Bars used:\t" << bars.size() << std::endl;
std::cout << "Total waste:\t" << totalWaste << " m" << std::endl;
std::cout << "Waste/Bar:\t" << totalWaste/bars.size() << " m" << std::endl;
std::cout << "===============================" << std::endl;
system("pause");
return 0;
}
}

[eduard77]

sorry I forgot the code

#include <iostream>
#include <iomanip>
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>
/* Get the number of different lengths from the user */
struct Cut{
    unsigned number;
	double length;
};
std::vector< Cut > allCuts;
Cut *currentCut;


int main () {
unsigned numberOfSizes;
std::cout << "Enter number of different sizes: ";
std::cin >> numberOfSizes;
 
/* Now get the actual numbers and lengths from the user */
for(unsigned i = 0; i < numberOfSizes; ++i){
	currentCut = new Cut;
    std::cout << "Enter new cut: <number> <length>" << std::endl;
	std::cin >> currentCut ->number >> currentCut->length;
    /* Check that the length is sensible */
    /*if((currentCut->length <= 0) || (currentCut->length > 12)){
        std::cerr << "Error length must be in the range (0,12]" << std::endl;
        --i;
    }
    else
        allCuts.push_back(currentCut);
}*/
 
/* Now put all the cuts into a single large vector */
std::vector< double > lengths;
for(unsigned i = 0; i < allCuts.size(); ++i){
    for(unsigned j = 0; j < allCuts[i].number; ++j)
        lengths.push_back(allCuts[i].length);
}
 
/* Sort the vector */
std::sort(lengths.begin(), lengths.end());
 
/* Make a place to put the lengths to cut from each bar */
const unsigned NEW_BAR_LENGTH = 12;
std::vector< std::vector< double > >bars;
std::vector< double > currentBar;
double remainingLength = NEW_BAR_LENGTH;
 
/* Now keep going through the lengths vector until all the cuts are accounted for */
while(lengths.size() > 0){
    /* start at the longest length that needs to be cut ... */
    std::vector< double >::iterator it = lengths.end() - 1;
    /* Go until the smallest length that's needed is reached */
    while(it >= lengths.begin()){
        /* Check if the current length will fit */
        if(*it < remainingLength){ /* If it will... */
            /* ... Add it to the current bar and remove it from the list to be fitted */
            currentBar.push_back(*it);
            /* Update the amount of the bar remaining */
            remainingLength -= *it;
            /* Remove the current element from the lengths vector */
           lengths.erase(it);
        }
        /* Check that we didn't just remove the last element */
        if(lengths.size() > 0){
            /* length[0] is the shortest length cut that we still need to get
               if this is more than the remaining amount of the current bar,
               then we should finish this bar and start a new one, check for
               this now */
            if(lengths[0] > remainingLength){
                /* Reset the remaining length */
                remainingLength = NEW_BAR_LENGTH;
                /* Add this completed bar to the vector of bars */
                bars.push_back(currentBar);
                /* Clear the current bar */
                currentBar.clear();
                /* Exit this loop and start on the new bar */
                break;
            }
        }
        --it;
    }
}

double totalWaste = 0.0;
for(unsigned i = 0; i < bars.size(); ++i){
    std::cout << "Bar " << std::setw(2) << i + 1 << ":\t";
    for(unsigned j = 0; j < bars[i].size(); ++j)
        std::cout << std::setprecision(3) << std::fixed << bars[i][j] << " ";
    std::cout << std::endl;
    std::partial_sum(bars[i].begin(), bars[i].end(), bars[i].begin());
    totalWaste += NEW_BAR_LENGTH - bars[i].back();
}
 
/* Print a summary */
std::cout << "===============================" << std::endl;
std::cout << "Bars used:\t" << bars.size() << std::endl;
std::cout << "Total waste:\t" << totalWaste << " m" << std::endl;
std::cout << "Waste/Bar:\t" << totalWaste/bars.size() << " m" << std::endl;
std::cout << "===============================" << std::endl;
system("pause");
return 0;
}
}

[ravenous]

Look at the lines 28 - 34. They check the input and then store it in the allCuts vector if it is good. For some reason you have commented them out?

You still have currentCut defined globally, and as a pointer. You should move the definition of currentCut and allCuts inside main() .

[eduard77]

I moved all in my main function but if i remove the pointer from *currentCut it gives me a lot of errors.
I uncommented from line 28 to line 34 but I receive the next error here:

else
        allCut.push_back(currentCut);
}

error C2664: 'void std::vector<_Ty>::push_back(_Ty &&)' : cannot convert parameter 1 from 'Cut *' to 'Cut

#include <iostream>
#include <iomanip>
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>
/* Get the number of different lengths from the user */




int main () {
	struct Cut{
    unsigned number;
	double length;
};
std::vector< Cut > allCuts;
Cut *currentCut;
unsigned numberOfSizes;
std::cout << "Enter number of different sizes: ";
std::cin >> numberOfSizes;
 
/* Now get the actual numbers and lengths from the user */
for(unsigned i = 0; i < numberOfSizes; ++i){
	currentCut = new Cut;
    std::cout << "Enter new cut: <number> <length>" << std::endl;
	std::cin >> currentCut ->number >> currentCut->length;
   /* Check that the length is sensible */
    if((currentCut->length <= 0) || (currentCut->length > 12)){
        std::cerr << "Error length must be in the range (0,12]" << std::endl;
        --i;
    }
    else
        allCut.push_back(currentCut);
}
 
/* Now put all the cuts into a single large vector */
std::vector< double > lengths;
for(unsigned i = 0; i < allCuts.size(); ++i){
    for(unsigned j = 0; j < allCuts[i].number; ++j)
        lengths.push_back(allCuts[i].length);
}
 
/* Sort the vector */
std::sort(lengths.begin(), lengths.end());
 
/* Make a place to put the lengths to cut from each bar */
const unsigned NEW_BAR_LENGTH = 12;
std::vector< std::vector< double > >bars;
std::vector< double > currentBar;
double remainingLength = NEW_BAR_LENGTH;
 
/* Now keep going through the lengths vector until all the cuts are accounted for */
while(lengths.size() > 0){
    /* start at the longest length that needs to be cut ... */
    std::vector< double >::iterator it = lengths.end() - 1;
    /* Go until the smallest length that's needed is reached */
    while(it >= lengths.begin()){
        /* Check if the current length will fit */
        if(*it < remainingLength){ /* If it will... */
            /* ... Add it to the current bar and remove it from the list to be fitted */
            currentBar.push_back(*it);
            /* Update the amount of the bar remaining */
            remainingLength -= *it;
            /* Remove the current element from the lengths vector */
           lengths.erase(it);
        }
        /* Check that we didn't just remove the last element */
        if(lengths.size() > 0){
            /* length[0] is the shortest length cut that we still need to get
               if this is more than the remaining amount of the current bar,
               then we should finish this bar and start a new one, check for
               this now */
            if(lengths[0] > remainingLength){
                /* Reset the remaining length */
                remainingLength = NEW_BAR_LENGTH;
                /* Add this completed bar to the vector of bars */
                bars.push_back(currentBar);
                /* Clear the current bar */
                currentBar.clear();
                /* Exit this loop and start on the new bar */
                break;
            }
        }
        --it;
    }
}

double totalWaste = 0.0;
for(unsigned i = 0; i < bars.size(); ++i){
    std::cout << "Bar " << std::setw(2) << i + 1 << ":\t";
    for(unsigned j = 0; j < bars[i].size(); ++j)
        std::cout << std::setprecision(3) << std::fixed << bars[i][j] << " ";
    std::cout << std::endl;
    std::partial_sum(bars[i].begin(), bars[i].end(), bars[i].begin());
    totalWaste += NEW_BAR_LENGTH - bars[i].back();
}
 
/* Print a summary */
std::cout << "===============================" << std::endl;
std::cout << "Bars used:\t" << bars.size() << std::endl;
std::cout << "Total waste:\t" << totalWaste << " m" << std::endl;
std::cout << "Waste/Bar:\t" << totalWaste/bars.size() << " m" << std::endl;
std::cout << "===============================" << std::endl;
system("pause");
return 0;
}

[ravenous]

error C2664: 'void std::vector<_Ty>::push_back(_Ty &&)' : cannot convert parameter 1 from 'Cut *' to 'Cut

Although these kind of error look scary and confusing, they're not. Take some time to think about what all the bits are:

void std::vector<_Ty>::push_back(_Ty &&)

this is obviously talking about the use of push_back() on line 35, so we know to look at that. The _Ty is the type that you're trying to push into your vector (so that would be something like int , std::string or, in your case, Cut . So, the next bit of the error:

cannot convert parameter 1 from 'Cut *' to 'Cut'

This is telling you what went wrong with push_back . When push_back is called in your code, it tries to add the variable that you give it to the end of the vector. All the elements in a vector must have the same type, so if the thing that you're pushing into the vector is not of the correct type then an implicit conversion is performed. If the compiler doesn't know how to convert to the right type, then you get this error. Basically, it's saying "I was expecting Cut but you gave me Cut * ". It was expecting something of type Cut because allCuts is declared as std::vector< Cut > , not as std::vector< Cut *> .

OK, so you have a number of problems here that require that you read about and try and understand the code that you have in front of you. Lines 1 to 36 should look like this:

#include <iostream>
#include <iomanip>
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>

struct Cut{
    unsigned number;
    double length;
};

int main () {
std::vector< Cut > allCuts;

Cut currentCut;    /* This is now just a regular variable, not a pointer */

unsigned numberOfSizes;
std::cout << "Enter number of different sizes: ";
std::cin >> numberOfSizes;
 
/* Now get the actual numbers and lengths from the user */
for(unsigned i = 0; i < numberOfSizes; ++i){
    currentCut = new Cut;
    std::cout << "Enter new cut: <number> <length>" << std::endl;
    /* because we changed currentCut to a regular variable, we use */
    /* the '.', not the '->' to access the members of currentCut   */
    std::cin >> currentCut.number >> currentCut.length;

   /* Check that the length is sensible */
    if((currentCut->length <= 0) || (currentCut->length > 12)){
        std::cerr << "Error length must be in the range (0,12]" << std::endl;
        --i;
    }
    else
        allCut.push_back(currentCut);
}

[eduard77]

That the program compile i had to remove "currentCut = new Cut;" .
When is running I after I enter the values I receive the next error:
vector iterator not decrementable

[ravenous]

I'm afraid I don't get this same error. It could be the compiler that particular implementation of the STL that you're using, or something else.

I think that the best idea would be to start a new thread that asks about this. Someone else will know more about it than me.