Suppose there is an unlimited number of pipes, each has length $x$ meters. There is a list of requirements of pipes with shorter length than $x$. The number of these items are also given.
For example we need to have $n_1$ pipes of length $x_1$,$n_2$ pipes of length $x_2$,..., $n_k$ pipes of length $x_k$ $\forall i, x_i \leq x$.
We need to cut the pipes of length $x$ such that the requirements to be fulfilled and also minimize the number of the used pipes.
For example for $x = 12$ and $$item1: x_1=3,n_1=50$$ $$item2: x_2=5,n_2=30$$ $$item3: x_3=7,n_3=80$$$$item4: x_4=2,n_4=90$$$$item5: x_5=9,n_5=15$$
we can cut the pipes in multiple ways. The worst solution is to allocate one pipe for each requirement, in this way the number of used pipes will be $$\sum_{i=1}^{i=k}{n_i} = 265$$
But by combining item2 and item3 into one pipe, we can reduce $256$ by $30$. In this way item2 is prepared then we can combine item1, item3 and item4 to prepare the items and use the minimum number of the pipes.
As another solution we can also combine item5 and item1, or even allocate one pipe of length $12$ for $4$ pipes of item1
I would like to know is this a famous problem? and is there any efficient algorithm for it?
My Solutions
Solution 1
Because I really don't know what the class of this problem is, I tried to solve this problem using the approximation algorithm given for the Set Cover problem.
The items form the set of elements, and any combination of items where the summation of their $x_i$ is less than or equal to $x$ is a valid set and its cost equals to $$cost(set_i) = x-\sum_{item_j \in set_i}{x_j} $$
But in set cover problem an element may appear in multiple sets while in this problem such thing is not reasonable. Besides that the $n_i$s are different that is why the Set Cover solution is not working here.
Solution 2
My second solution is a simple greedy algorithm. First I create set of valid sets as explained in the Solution 1, select the one with minimum cost. In this way at least one item with the minimum $n_i$ is produced.
In the second step, first I need to update $n_i$s (because some items are produced in the previous step) and remove the completely covered item from the list. If $set_j$ was the set with minimum cost, Then there will be a few pipes with the length $$wasted= x - \sum_{item_k \in set_j}{x_k}$$.
For the remaining items in the list, if there is anyway to form elements in a set such that sum of their $x_i$ is less than or equal to $wasted$ then we produce those pipes, else we should repeat from the first step with the new list.
