crh40 / ClothCutter

You are given a rectangular piece of cloth with dimensions X by Y, where X and Y are positive integers, and a list of n products that can be made using the cloth. For each product i in [1,n] you know that a rectangle of cloth of dimensions ai by bi is needed and that the final selling price of the product is ci. Assume that ai, bi, and ci are all positive integers. You have a machine that can cut any rectangular piece of cloth into two pieces either horizontally or vertically. Design an algorithm that finds the best strategy for cutting an X by Y piece of cloth so that the products made from the resulting pieces give the maximum sum of selling prices. You are free to make as many copies of a given product as you wish, or none if desired.