title: Dynamic Programming and Knapsack Application
body: <p>Im studying dynamic programming and am looking to solve the following problem, which can be found here <a href="http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf">http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf</a>:</p>
  
  <p>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. (From Algorithms by Dasgupta, Papadimitriou, and Vazirani.)</p>
  
  <p>It seems we have a sort of 2-dimensional knapsack problem, but I'm thinking it may be possible to just solve it with the traditional knapsack algorithm by considering the weights as the areas of the rectangles.  Does this seem like a reasonable approach?</p>
  
  <p>This is a programming assignment for a course I'm taking so please only include conceptual discussion and/or pseudo-code to illustrate ideas.</p>