Solved

Optimal problem

Posted on 2004-10-13
230 Views
Last Modified: 2010-04-17
Hi experts,
I'm facing with a problem below: I have a rectangular plank and a few of pieces of paper. I stick these pieces of paper on the plank and cut the plank following these pieces. How can I find out a way to stick the pieces on the plank so that the remainder of the plank is optimal.
Who can tell me some books or some components that help me to resolve this problem?
Thanks.
0
Question by:rock2003
5 Comments

LVL 6

Expert Comment

Take a look at his link ...
http://matheron.uv.es/investigar/tr01-04.pdf
hope can help you ...
0

LVL 1

Accepted Solution

Mistobaan earned 500 total points
The first place to look is : http://www.cs.sunysb.edu/~algorith
Maybe is usefull: http://www.cs.sunysb.edu/~algorith/files/polygon-partitioning.shtml
But I think that your one is a kind of "Hard Problem" also know as NP. It seems like a Bin-packing ( also know as Knapsack problem ) but with areas instead of weight, plus shape matching...
you can find some topics about this kind of problem on :
http://www.ifors.ms.unimelb.edu.au/tutorial/knapsack/

0

LVL 3

Expert Comment

Can the paper pieces be of any shape? irregular..??
0

Author Comment

Yes, kumvjuec. The paper pieces can be any shape (rectangle, triangle, circle...).
0

LVL 6

Expert Comment

A sub-optimal solution could be aproximate your shapes with their bounding-box ...

Have you already choosen a cost-function to evaluate the godness of your pieces placing?
0

Join & Write a Comment Already a member? Login.

Suggested Solutions

This article will show, step by step, how to integrate R code into a R Sweave document
Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!