Solved

Optimal problem

Posted on 2004-10-13
5
234 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
ID: 12296021
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
ID: 12296763
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
ID: 12311004
Can the paper pieces be of any shape? irregular..??
0
 

Author Comment

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

Expert Comment

by:mmusante
ID: 12316525
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
groupSumClump challenge 9 103
Turning python script into an applet 12 105
Modify a small python script 19 97
Q2. How to run DAX query from SSMS. I don’t see any DAX query type. 1 49
Whether you've completed a degree in computer sciences or you're a self-taught programmer, writing your first lines of code in the real world is always a challenge. Here are some of the most common pitfalls for new programmers.
Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
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…

863 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

23 Experts available now in Live!

Get 1:1 Help Now