圆中矩形的最大堆积
我在一家纳米技术实验室工作，负责硅晶圆切割。 （晶圆锯仅切割平行线）当然，我们正在努力最大化我们切割的芯片的产量。所有芯片的尺寸都相同，无论是矩形还是正方形，并且芯片都是从圆形晶圆上切下来的。本质上，我试图将最大的矩形打包成一个圆。
我对 MATLAB 只有相当基本的了解，对微积分只有中级了解。有没有（相对）简单的方法可以做到这一点，还是我超出了我的能力范围？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
从这里开始，祝你好运：
http://en.wikipedia.org/wiki/Knapsack_problem
并到达这里：
http://www-sop.inria.fr/mascotte/WorkshopScheduling /2Dpacking.pdf
至少你会知道你在这里要解决什么问题。
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.
我很着迷地读到你的问题，因为我为数学老师的培训做了一个关于这个的项目。我也很高兴知道它被认为是一个 NP 问题，因为我的项目使我得出了同样的结论。
通过使用基本微积分，我计算了最大尺寸矩形的前几“代”，但它很快就变得复杂。
您可以在这里阅读我的项目：
我希望我的一些发现对您有用或者至少有趣。我认为这个想法的应用最有可能是在计算机纳米技术中。
亲切的问候。
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:
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.
将任意矩形打包成圆形以满足空间效率目标通常是一种非凸（NP-Hard）优化。这意味着没有优雅或简单的解决方案可以最佳地解决这个问题。解决方案方法都将取决于您可以用来修剪搜索树或开发启发式方法的任何特定领域知识。如果您没有解决此类问题的经验，您可能应该咨询专家。
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.
这不是很像高斯圆问题吗？看
http://mathworld.wolfram.com/GausssCircleProblem.html
或者，这可以看作是「包装问题」
http://en.wikipedia.org/wiki/Packing_problem#Squares_in_circle
doesn't this resemble the Gauss's Circle Problem? See
http://mathworld.wolfram.com/GausssCircleProblem.html
or, this can be seen as a "packaging problem"
http://en.wikipedia.org/wiki/Packing_problem#Squares_in_circle