在圆形中最大矩形的堆叠

Question

9

我在一个纳米技术实验室工作，从事硅晶圆切割工作。（晶圆锯只能切平行线）我们当然要最大化切割出的晶片产量。所有的晶片都是相等大小的，可以是矩形或正方形，并且这些晶片都是从一个圆形晶圆中切割而来的。本质上，我正在尝试将最大数量的矩形装入一个圆形中。

我只有基本的MATLAB理解和中级的微积分知识。是否有（相对）简单的方法来做到这一点，还是我太难了？

- Patrick

2

除了Matlab语法之外，您可能还想考虑使用http://math.stackexchange.com/和http://mathoverflow.net/来解决问题的微积分部分。 - John K

2

我不确定你的问题是什么。但是，当正方形/矩形的大小趋近于零时，它们在圆形内的装箱效率接近100%。 - Oliver Charlesworth

似乎是背包问题的一个有趣变体。http://en.wikipedia.org/wiki/Knapsack_problem - Daniel Mošmondor

据我理解，他有一些矩形（全部都是固定大小），他试图将它们装入一个同样固定大小的圆中。如果这些矩形的大小都不同，那么这可能是一个 NP 问题。但由于它们都是相同的大小，这实际上是可行的。 - nsanders

4个回答

1

从这里开始，祝你好运：

并在这里获得：

至少你会有一些关于你在这里处理什么的想法。

- Daniel Mošmondor

0

- Fredrik Pihl

0

将任意矩形装入圆形以满足空间效率目标通常是一个非凸（NP-难）优化问题。这意味着没有优雅或简单的解决方案可以最优地解决此问题。解决方法都将取决于您可以使用的特定领域知识来修剪搜索树或开发启发式算法。如果您没有此类问题的经验，建议咨询专家。

- fairidox

1

OP说：“所有的骰子都将是相等大小的，无论是矩形还是正方形。” 这并不是那么难。 - j_random_hacker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rachel Beckett · Accepted Answer

我很着迷地阅读了你的问题，因为我在成为数学教师的培训中做过这个项目。我也很高兴知道它被认为是一个NP问题，因为我的项目也得出了同样的结论。

通过使用基本微积分，我计算了最大尺寸的前几个“代”的矩形，但它很快变得复杂起来。

你可以在这里阅读我的项目：

贝克特，R. 派的包装问题。巴斯温泉MEC。2009年。

我希望我的一些发现对您有用或者至少是有趣的。我认为这个想法的应用最有可能在计算机纳米技术领域。

此致敬礼。