Solved

Optimal problem

Posted on 2004-10-13
5
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
Comment
Question by:rock2003
5 Comments
 
LVL 6

Expert Comment

by:mmusante
Comment Utility
Take a look at his link ...
http://matheron.uv.es/investigar/tr01-04.pdf
hope can help you ...
0
 
LVL 1

Accepted Solution

by:
Mistobaan earned 500 total points
Comment Utility
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

by:kumvjuec
Comment Utility
Can the paper pieces be of any shape? irregular..??
0
 

Author Comment

by:rock2003
Comment Utility
Yes, kumvjuec. The paper pieces can be any shape (rectangle, triangle, circle...).
0
 
LVL 6

Expert Comment

by:mmusante
Comment Utility
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

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

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.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now