Optimal cuts from pipe I need to make a program that calculates the optimal way to cut pieces of pipe to what a customer wants.
My advanced math skills are bad but I know this is the cutting stock problem. My first problem is that I don't really understand much on that wikipedia page. The other thing is that the page describes solving this problem when all the pieces you have in inventory are the same size. How do you optimize when you have varying sizes in inventory and you want to use up the small ones first?
For example say we have pieces of this length in inventory:
2', 18'
And a customer wants these lengths:
1', 12'
My understanding of the wikiepdia page is that it is trying to reduce the left over(waste) which would mean that you would take the requested 1', 12' out of the 18' to have a left over of 5'.
The optimal solution I would want is to take 1' out of the 2' and 12' out of the 18' even though the total left over is 7' because we want to keep pieces as long as possible.
I am having a hard time describing this. Any general guidance on this would be great.
 A: I assume you are trying to maximize the length of the shortest resulting pipe, breaking ties by going to the second shortest pipe, third shortest, etc. Luckily this is a much easier problem than the cutting stock problem, and in fact can be solved by a greedy algorithm. All you need to do is take the longest cut from the longest pipe remaining. More formally, let $P$ be the set of pipes and $C$ the set of cuts, and perform the following:


*

*Remove the largest cut $c$ from $C$.

*Cut the largest pipe $p$ in $P$, and replace $p$ with $p-c$ in $P$.

*If $C$ is not empty, go to step 1.


Proof of correctness: Clearly this is correct if $C$ consists of just $1$ cut. Assume it is correct for all sets of $n$ cuts, and let $C$ consist of $n+1$ cuts. Let $P'$ be the optimal set of pipes after all cuts have been performed, and $P''$ be the same set of pipes, but before the last cut. By assumption, by the time the algorithm reaches its last iteration we will have $P=P''$. But since it is optimal to cut the largest pipe any time we have only one cut to make, the algorithm must produce exactly $P'$ after the last iteration. Thus by induction the algorithm is correct.
A: @mike
I'll try


*

*Let P' be the set of all pipes longer than c

*Cut the shortest pipe in P'.

*Go to step 1


To avoid too much scrap
