lمسئله چوب بری در حالت کلی به این صورت است:میخواهیم یک قطعه چوب به طول l متر را از نقاط [tex]x_{1}[/tex] تا [tex]x_{n-1}[/tex]
که [tex]x{k}[/tex] فاصله ی نقطه ی برش k ام از انتهای چپ قطعه چوپ است ببریم(فرض [tex]x_{0}=0[/tex]
و [tex]x_{n}=l[/tex])هزینه برش یک قطعه چوب به اندازه m متر از هر نقطه آن نقطه برابر m تومان (و مستقل از مکان نقطه ای برش) است.زیر مسئله [tex]p_{ij}[/tex] [tex]\left ( i<j \right )[/tex] را قطعه چوب بین نقاط [tex]x_{i}[/tex] و [tex]x_{j}[/tex] میگیریم که باید از نقاط [tex]x_{i 1}[/tex]تا [tex]x_{j-1}[/tex] بریده میشود.مسئله اصلی [tex]p_{0 n}[/tex] h اگر r اولین نقطه ی برش برای [tex]p_{ij}[/tex] و [tex]c_{ij}[/tex] کمیته ی هزینه ی این زیر مسئله باشد ،[tex]c_{ij}[/tex] برابر کدام یک از رابطه های زیر است؟؟(بدیهی است که [tex]c_{ii}=c_{i,i 1}=0[/tex]


جواب:
[tex]min_{i<r<k}(c_{ir} c_{r 1,j} x_{j}-x_{i})[/tex]



می خواهیم چوبی به اندازه ۲۹ متر را از نقاط ۴و۱۴و۱۹و۲۷ متری(نسبت به سر سمت چپ چوب)به ۵ قسمت تقسیم تقسیم میکنیم.همچنین فرض کنید که هزینه برش یک قطعه چوب به اندازه k متر از هر نقطه آن نقطه برابر k تومان (و مستقل از مکان نقطه برش) است.در این صورت هزینه کمینه برای برش چوب داده شده چقدر است؟؟توجه کنید که ترتیب برش هزینه های مختلفی ایجاد میکند.
جواب:۵۴

این تست شبیه تست مهندسی کامپیوتر ۸۷ که گفته یه تیر چوبی به طول L متر داریم اونجا جوابشو تو پوران گفته تداعی کننده درخت BST بهینه هست،اما با توجه به اون چجوری میشه ۵۴??