可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效，请关闭广告屏蔽插件后再试):

问题:

I work at a nanotech lab where I do silicon wafer dicing. (The wafer saw cuts only parallel lines) We are, of course, trying to maximize the yield of the die we cut. All the of die will be equal size, either rectangular or square, and the die are all cut from a circular wafer. Essentially, I am trying to pack maximum rectangles into a circle.

I have only a pretty basic understanding of MATLAB and an intermediate understanding of calculus. Is there any (relatively) simple way to do this, or am I way over my head?

回答1:

Go from here, and good luck:

http://en.wikipedia.org/wiki/Knapsack_problem

and get here:

http://www-sop.inria.fr/mascotte/WorkshopScheduling/2Dpacking.pdf

At least you'll have some idea what are you tackling here.

回答2:

I was fascinated to read your question because I did a project on this for my training as a Mathematics Teacher. I'm also quite pleased to know that it's thought to be an NP-problem, because my project was leading me to the same conclusion.

By use of basic calculus, I calculated the first few 'generations' of rectangles of maximum size, but it gets complex quite quickly.

You can read my project here:

Beckett, R. Parcels of Pi: A curve-packing problem. Bath Spa MEC. 2009.

Pages 1 - 15

Pages 16 - 30

I hope that some of my findings are useful to you or at least interesting. I thought that the application of this idea would most likely be in computer nano technology.

Kind regards.

回答3:

Packing arbitrary rectangles into a circle to meet a space efficiency objective is a non-convex (NP-Hard) optimization in general. This means there will be no elegant or simple solution that will solve this problem optimally. The solution methods are all going to depend on any specific domain knowledge you can use to prune the search tree or develop heuristics. If you have no experience in this type of problem you should probably consult with an expert.