do test only use techniqes found in files

Cutting stock problem

												Pattern	1	2	3	4	5	6
												# rolls to cut	72	211	0	56	0	0
												12 in.	0	0	1	9	2	7		504	>=	500
												15 in.	7	1	0	0	1	1		715	>=	715
												30 in.	0	3	3	0	2	0		633	>=	630
												scrap	5	5	8	2	11	11	total scrap	1527	MIN
			Pattern	12 in.	15 in.	30 in.	scrap
			1	0	7	0	5
			2	0	1	3	5
			3	1	0	3	8
			4	9	0	0	2
			5	2	1	2	11
			6	7	1	0	11

A company makes 110-inch-wide rolls of sheet metal, which it slices into smaller rolls to meet customer orders for widths of 12, 15, and 30 inches. Of course, there are many ways of cutting these widths from a 110-inch-wide roll. The company comes up with the cutting patterns shown below, which include the leftover material (scrap). Suppose we have orders for 500 12-inch rolls, 715 15-inch rolls, and 630 30-inch rolls. We would like to determine how many rolls should be cut according to each pattern so that we minimize waste yet fill all customer orders.

Another example

								patterns	1	2	3	4	5	6	7	8
									8	0	5	4	0	0	0	0
								6 in	2	1				1		3		16	>=	15
								8 in	1			1	2		1			12	>=	10
								10 in			2			1	1			10	>=	9
								12 in		1		1						4	>=	4
								scrap	0	2	0		4	4	2	2	total scrap	0	MIN

This time we have 20-inch sections of metal pipe. We have orders for the following lengths: 6 in. (quantity 15) 8 in. (quantity 10) 10 in. (quantity 9) 12 in. (quantity 4) First, figure out all possible cutting patterns. Then, complete the orders while minimizing the scrap.