# Determine no of combinations for cutting stock algorithm

I have to buy $n$ wooden logs of size 2000 each, from which I have to cut different pieces of smaller size say:

255*10
750*7
550*13


In a manner that cutting will cause minimum no of purchases ($n$) and minimum wastage.
I found a similar problem in wikipedia (click this link) which gives an example(see in the link) and says:

"There are 308 possible patterns for this small instance. The optimal answer requires 73 master rolls and has 0.401% waste"

I want to know how it calculated the no of combinations to be 308.

In the example on Wikipedia that you cite, there are 13 different lengths, ranging from 1380 to 2200, that must be cut from rolls that are 5600. Some of the 308 patterns that may be cut are: $4\times 1380$, $2\times 2200$, $1380+2150+1930$. I'm sure that they simply exhaustively computed 308 with a few lines of code, but one could also do a tedious case analysis. For example:

Let's count the number of patterns that include $2200$ as their largest number. That leaves $5600-2200=3400$, so if the second-largest is in $\{2050, 2100, 2140, 2150, 2200\}$ there isn't room for a third number. If the second-largest number is in $\{2000, 1930\}$ there is room for $1380$ as the third number. If the second-largest number is $1880$, there is room for either $1380$ or $1520$ as the third number. If the second-largest number is $1820$ or $1710$ or $1560$, there is room for any of $\{1380, 1520, 1560\}$ to be the third number. If the second-largest number is $1520$, then either $1520$ or $1380$ may be the third number. Lastly, the second and third numbers could both be $1380$. Counting all of these gives $21$ patterns have $2200$ as their largest number.

• I created a program for it. It have initially the count of pieces to be cut, Then finds the best combination suited for cut(ex-2150+1930+1520) and the reduce pieces from calculated combination from stock and then again search for best combination until all pieces are finished. This algo fails, as it required 75 pieces for the same wiki example which required 73 pieces. But this method creates maximum no of perfect cuts(whole 5600 piece is used). See here the result of my algo. Here is my running web program – Gaurav Sharma Apr 28 '13 at 9:45
• yes,but i wanted to know about some mathematical equation to find 308. Thanks anyway. – Gaurav Sharma Apr 28 '13 at 16:53

I had a misunderstanding. I thought 308 is the no of combinations for making all rolls as given in data and one of the 308 combination is the optimal answer given there, but now I have understood that 308 is the no of combinations for making use of the first 5600 width roll. Example

1380
1380+1380
1380+1380+1380
1380+1380+1380+1380
1380+1380+1520
.
..


and so on, 308 combinations are possible.
I verified it by making a java program to calculate combinations in this manner which gave result 308.

class Pappu
{
static int total,comb[],max[],count=0;
public static void main(String ...s)
{
int maxlen=5600;
int arr[]={2200,2150,2140,2100,2050,2000,1930,1880,1820,1710,1560,1520,1380};
int qty[]={20,18,16,14,12,10,20,18,18,14,12,25,22};
boolean chaloo=true;
int sum=0;
total=arr.length;
max=new int[total];
comb=new int[total];
for(int i=0;i<total;i++)  //calculating upper bound of combination
{
max[i]=maxlen/arr[i];
}
while(chaloo)
{
combinations();
for(int i=0;i<total;i++)
sum+=arr[i]*comb[i];
if(sum<=maxlen)
count++;    //counting only those combination which can be cut from size under 5600
sum=0;
for(int i=0;i<total;i++)
{
if(comb[i]!=max[i])
{
chaloo=true;
break;
}
chaloo=false;
}
}
System.out.println(count);
}
/* combination generated are of form
0000000000001
0000000000002
0000000000003
.....
0000000000010
0000000000011
.....
till upeer bound of max[]
*/
static void combinations() //combination generator
{
for(int i=total-1;;)
{
if(comb[i]!=max[i])
{
comb[i]++;
break;
}
else
{
if(i==0 && comb[0]!=max[0])
i=total-1;
else
{
comb[i]=0;
i--;
}
}
}
}
}