Solved

Optimal problem

Posted on 2004-10-13
5
237 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

Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Magic Software info 18 130
Math Question 1 91
Beginner to Unreal Engine 4 5 79
Android development question 2 35
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
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 …

785 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