Algorithm for cutting rods with minimum waste


Given a set of cuts and their lengths we need to find out the minimum number of rods (of constant length) and the cuts required which will lead to minimum wastage.

Here we bundle the rods and cut them all at once. So we can have a bundle with any number of rods.

For example:

Input data – Consider a rod of length 120 inches

( Quantity of Cuts Required, Length (in inches) ) = (5,16") , (5,30") , (24,36") , (4,18") , (4,28") , (6,20")

So here we required cuts such that we get 5 rods of 16 inches, 5 rods of 30 inches..so on.

Output:

Imagine each row (in the image) is a rod of 120 inches and each table is a bundle with rows as the number of rods in that bundle. So the first table is a bundle with 5 rods with cuts [16,30,36,36] and second table is a bundle of 4 rods with cuts [18,28,36,36] and so on. We can see that we have satisfied the input data we get (5,16") five rods of sixteen inches and so on.

enter image description here

Given input with (just like above) number of cuts and their lengths. how do we find the bundle of rods and their cuts having minimum amount of wastage?